Graphs with valency k, edge connectivity k, chromatic index k + 1 and arbitrary girth

✍ Scribed by V. Faber; J. Mycielski

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 561 KB
• Volume: 4
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(73)90168-4

✦ Synopsis

We prove thbt if k>3 and there exists a regular graph with valency k, edge ity k and chromatic index k +l, then there exists such a graph of any girth g 14. connectiv-G=(X.E)iscalledagraph ifXisafinitesetandEc {{xr,.x2)lx1, x2 E X and x1 # x2 ). We call X the set of vertices and E the set of edges of G. For each x E X, d(x) is the number of edges containing x. We call d(x) the valency of the vertex x. If d(x) is the same for all x E X, then G is called regular. G has edge connectivity k if k is the smallest number of edges whose removal disconnects G. G has chromatic index h if its edges can be partitioned into X disjoint classes (colors), but no fewer, so that two edges of the same class (color) have no common vertices. G has girth g if no cycle has length shorter than g. If x E X, G, denotes the graph with vertex set H(x) and edge set {e E Elx $ e}. I G I denotes the cardinality of X. Further definitions may be found in [2] or 161.

The Petersen graph (see Fig. ) is bridgeless (that is, it has edge connectivity at least 2), r.rivalent, of girth 5 and has chromatic index 4. In this paper we prove