Edge-Coloring of Split Graphs

Abstract

The Classification Problem is the problem of deciding whether a simple graph has chromatic index equal to $\mathrm{\Delta }$ or $\mathrm{\Delta }+1$, where $\mathrm{\Delta }$ is the maximum degree of the graph. It is known that deciding if a graph has chromatic index equal to $4$ is $NP$-complete. A split graph is a graph whose vertex set admits a partition into a stable set and a clique. The chromatic indexes for some subsets of split graphs, such as split graphs with odd maximum degree and split-indifference graphs, are known. However, for the general class, the problem remains unsolved. In this paper, we exhibit a new subset of split graphs with even maximum degree that have chromatic index equal to $\mathrm{\Delta }$. Moreover, we present polynomial-time algorithms to perform an edge-coloring and to recognize these graphs.