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 ...
Curran, Paul G. (Monterey, California. Naval Postgraduate School, 1997-09);For centuries, military forces have used camouflage to obscure potential targets from the enemy. Because the eye is fairly adept at picking out edges, colors, and bright areas, camouflage is often used to degrade these ...
Experimental determination of paraxial ray transfer matrices and cardinal points of complex optical systems by means of finite conjugate imaging Blackwell, Jerry S. (Monterey, California. Naval Postgraduate School, 2001-12);The Lineate Imaging Near-ultraviolet Spectrometer (LINUS) uses three complex lens systems to focus an image from distances on the order of several kilometers onto the image intensifier of an ultraviolet camera. These images ...