How to find overfull subgraphs in graphs with large maximum degree (Q1329811)

Let \(G=G(V,E)\) be a simple graph, \(\chi'(G)\) and \(\Delta(G)\) be its chromatic index and the maximum degree of its vertices, respectively. \(G\) is said to be overfull, if \[ E \geq \left \lfloor {| V | \over 2} \right \rfloor \Delta (G) + 1, \] and it is known that in this case \(\chi'(G)=\Delta(G)+1\). This sufficient condition can be generalized in the manner that the existence of an induced and overfull subgraph \(H\) of \(G\) with \(\Delta (H) = \Delta (G)\) implies \(\chi' = \Delta (G) + 1\); in such case \(H\) is said to be overfull in \(G\). There is a conjecture that for graphs with \(2\Delta (G) \geq | V(G) |\) holds \(\chi' = \Delta + 1\) iff \(G\) has an overfull subgraph \(H\) with \(\Delta (H) = \Delta (G)\); and therefore in this paper a fast algorithm is presented for finding such subgraphs, if they exist. In Section 2, some conditions for overfull graphs \(G\) and subgraphs \(H\) are proved in form of inequalities depending on \(| E |\), \(| V |\), \(\Delta\) and on certain properties of the neighborhood of vertices. Applying these results in Section 3 three theorems are proved which yield the theoretical base of the algorithm. This algorithm consists of four steps, which are described in detail, and the author shows that the vertex set of every overfull subgraph \(H\) of the input graph \(G\) is determined in fact in Step 4. Finally, he proves that in the case of graphs \(G\) with \(2\Delta (G) \geq | V(G) |\), there exists at most one subgraph overfull in \(G\) (Theorem 3.4).