CHARACTERIZING AND EDGE-COLORING SPLIT-INDIFFERENCE GRAPHS

We describe a simple characterization of graphs which are simultaneous ly split and indifference graphs. In the sequel, we present a method f or optimally edge colouring a complete graph with an even number great er than or equal to 6 of vertices, leading to a simple construction fo r exhibiting a perfect matching of it, in which all its edges have dif ferent colours. Based on the two results, we obtain equations for comp uting the chromatic index of graphs of the considered class, in linear time. We recall that the chromatic index problem is still unsolved fo r both classes of split and indifference graphs. (C) 1998 Elsevier Sci ence B.V. All rights reserved.