Chromatic numbers of competition graphs
Merz, Sarah K.
Rasmussen, Craig W.
Lundgren, J. Richard
MetadataShow full item record
Previous work on competition graphs has emphasized characterization, not only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of characterization 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 F, does the structure of G tell us anything about the chromatic number X of the competition graph C(G)? We show that in some cases we can calculate this chromatic number exactly, while in others we can place tight bounds on the chromatic number.
Approved for public release; distribution is unlimited.
NPS Report NumberNPS-MA-93-020
Showing items related by title, author, creator and subject.
Lundgren, J. Richard; Merz, Sarah K.; Rasmussen, Craig W. (North-Holland, 1995);Previous work on competition graphs has emphasized characterization, not only of the competition graphs themselves but also of those graphs whose competition graphs are chordal or interval. The latter sort of characterization ...
A graph theoretic approach to the optimal slot utilization problem for naval communication networks Bell, Pamela K. (Monterey, California. Naval Postgraduate School, 1992-06);This paper approaches the optimal slot utilization problem in a Naval Battle Group by modelling ships capable of transmitting on a particular frequency as vertices in a graph, and the relationships between them as edges ...
Lundgren, J. Richard; Merz, Sarah K.; Maybee, John S.; Rasmussen, Craig W. (Norrth-Holland, 1995);One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless ...