The Overfull Conjecture on split-comparability and split-interval graphs

An edge-coloring of a graph G is an assignment of colors to the edges of G so that adjacent edges have distinct colors. The chromatic index chi '(G) is the smallest number of colors needed in an edge-coloring of G. Clearly, chi '(G) >= Delta(G) and the celebrated Vizing's Theorem (1964) states that chi '(G) <=Delta(G)+1, for any simple graph G. A simple graph G is Class 1 if chi '(G) = Delta(G), and Class 2 otherwise. The Classification Problem is to determine whether a simple graph is Class 1. The Overfull Conjecture, proposed by Chetwynd and Hilton (1984), states that when Delta(G) > vertical bar V(G)vertical bar/3, the graph G is Class 1 if and only if it is not subgraph-overfull. Figueiredo et al. (2000) conjectured that any chordal graph is Class 1 if and only if it is not subgraph-overfull. Chordal graphs are a superclass of split and of interval graphs. In this paper we prove that both the Overfull and Figueiredo et al.'s Conjectures hold for all split-comparability and split-interval graphs. Our proofs lead to polynomial-time algorithms to solve the Classification Problem in these classes. (C) 2023 Elsevier B.V. All rights reserved.