The overfull conjecture on split-comparability and split-interval graphs (Q6048434)

By Vizing's well-known edge coloring theorem the chromatic index \(\chi^\prime(G)\) of a graph \(G\) satisfies \(\chi^\prime(G) =\Delta(G)\) or \(\chi^\prime(G) = \Delta(G)+1\), where \(\Delta(G)\) as usual denotes the maximum degree of a graph \(G\). Graphs with chromatic index \(\Delta(G)\) are called Class 1, and those with \(\Delta(G)+1\) are called Class 2. A graph \(G\) is overfull if it has more than \(\Delta(G) \lfloor |V(G)| /2 \rfloor\) edges; such graphs are Class 2. A graph \(G\) is subgraph-overfull if it has a subgraph \(H\) such that \(\Delta(H) = \Delta(G)\) and \(H\) is overfull. \(G\) is neighborhood-overfull if some vertex of maximum degree satisfies that the subgraph induced by its closed neighborhood is overfull. \textit{A. G. Chetwynd} and \textit{A. J. W. Hilton} [J. Graph Theory 8, 463--470 (1984; Zbl 0562.05024)] conjectured that if \(G\) is a graph with \(\Delta(G) > |V(G)|/3\), then \(G\) is Class 1 if and only if it is not subgraph-overfull. Later on, \textit{C. M. H. de Figueiredo} et al. [J. Comb. Math. Comb. Comput. 32, 79--91 (2000; Zbl 0981.05045)] conjectured that if \(G\) is chordal, then it is Class 1 if and only if it is not subgraph-overfull. In the paper under review, the authors verify that both conjectures hold for two families of chordal graphs: graphs which are both split graphs and interval graphs, and graphs which are both split graphs and comparability graphs. The proofs of the results are based on the structural properties of these classes and yield polynomial-time algorithms for deciding whether a graph from these families is Class 1 or Class 2.