Local Conditions for Edge-Coloring

Abstract

In this note, we investigate three versions of the overfull property for graphs and their relation to the edge-coloring problem. Each of these properties implies that the graph cannot be edge-colored with $\mathrm{\Delta }$ colors, where $\mathrm{\Delta }$ is the maximum degree. The three versions are not equivalent for general graphs. However, we show that some equivalences hold for the classes of indifference graphs, split graphs, and complete multipartite graphs.