Regular graphs and edge chromatic number (Q790826)

For a simple graph \textit{G. Vizing}'s Theorem [On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3, 25-30 (1964)] implies that \(\Delta(G)\leq \chi(G)\leq \Delta(G)+1,\) where \(\Delta\) (G) is the maximum degree of a vertex in G and \(\chi\) (G) is the edge chromatic number of G. It is, of course, possible to add edges to G without changing its edge chromatic number. In fact, any graph G is a spanning subgraph of an edge maximal graph \(G^*\) such that \(\chi(G^*)=\chi(G)\). The question addressed here is when there exists such a graph \(G^*\) which is \(\chi\) (G)-regular. Theorem. If \(n\geq 2(k^ 2-k+1),\) n is even, \(k\geq 2\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \((k+1)\)-regular graph \(G^*\) with \(\chi(G^*)=k+1.\)- Conjecture. If \(n\geq 2k\), n is even, \(k\geq 2\) and G is a connected k-regular graph with n vertices, then G is a spanning subgraph of a \((k+1)\)-regular graph \(G^*\) with \(\chi(G^*)=k+1\) except when \(G=K_{k,k}\) and k is odd.