Using Latin Squares to Color Split Graphs

An \emph{edge-coloring} of a graph is an assignment of colors to its edges such that no adjacent edges have the same color. A \emph{split graph} is a graph whose vertex set admits a partition into a stable set and a clique. Split graphs have been introduced by Földes and Hammer and it is a well-studied class of graphs. However, the problem of deciding the chromatic index of any split graph remains unsolved. Chen, Fu, and Ko use a latin square to color any split graph with odd maximum degree. In this work, we also use a latin square to color some split graphs with even maximum degree and we show that these graphs are Class 1.

2009