Edge-Coloring of Split Graphs

The {\em Classification Problem} is the problem of deciding whether a simple graph has chromatic index equals to $\Delta$ or $\Delta+1$, where $\Delta$ is the maximum degree of the graph. It is known that to decide if a graph has chromatic index equals to $\Delta$ is NP-complete. A {\em 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 $\Delta$. Moreover, we present polynomial time algorithms to perform an edge-coloring and to recognize these graphs.

2009