CHROMATIC-NUMBERS OF COMPETITION GRAPHS

Previous work on competition graphs has emphasized characterization, n ot only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of c haracterization is of interest when a competition graph that is easily colorable would be useful, e.g. in a scheduling or assignment problem . This leads naturally to the following question: Given a graph G, doe s the structure of G tell us anything about the chromatic number chi o f the competition graph C(G)? We show that in some cases we can calcul ate this chromatic number exactly, while in others we can place tight bounds on it.