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 ca lled overfull if \E(G)\ > Delta(G)[\V(G)\/2]. A sufficient condition f or chi'(G)= Delta(G) + 1 is that G contains an overfull subgraph H wit h Delta(H)= Delta(G). Plantholt proved that this condition is necessar y for graphs with a universal vertex. In this paper, we conjecture tha t, for indifference graphs, this is also true. As supporting evidence, we prove this conjecture for general graphs with three maximal clique s and with no universal vertex, and for indifference graphs with odd m aximum degree. For the latter subclass, we prove that chi' = Delta.