ON EDGE-COLORING INDIFFERENCE GRAPHS

Vizing's theorem states that the chromatic index chi'(G) of a graph G is either the maximum degree Delta(G) or Delta(G) + 1. A graph G is called overfull if \E(G)\ > Delta(G)right perpendicular\V(G)\/2 left perpendicular. A sufficient condition for chi'(G) = Delta(G) + 1 is that G contains an overfull subgraph H with Delta(H) = Delta(G). Plantholt proved that this condition is necessary for graphs with a universal vertex. In this paper, we conjecture that, for indifference graphs, this is also true. As supporting evidence, we prove this conjecture for general graphs with three maximal cliques and with no universal vertex, and for indifference graphs with odd maximum degree. For the latter subclass, we prove that chi' = Delta.