Regular graphs and edge chromatic number

✍ Scribed by R.J Faudree; J Sheehan

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 376 KB
• Volume: 48
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90182-1

✦ Synopsis

For any simple graph G, Vizing's Theorem [5] implies that A (G)~)((G)<~ A(G)+ 1, where A (G) is the maximum degree of a vertex in G and x(G) is the edge chromatic number. It is of course possible to add edges to G without changing its edge chromatic number. Any graph G is a spanning subgraph of an edge maximal graph G* such that x(G*) = x(G). Does there always exist such a graph G* which is x(G)-regular?

We prove that if n ~> 2(k 2 -k + 1), n is even, k ~> 2 and G is a connected k-regular graph on n vertices, then G is a spanning subgraph of a (k + 1)-regular graph G* with x(G*)= k + 1.