Chromatic numbers of competition graphs
By: by J. Richard Lundgren, Sarah K. Merz, Craig W. Rasmussen
Contributors: Merz, Sarah K.; Rasmussen, Craig W.; Naval Postgraduate School (U.S.). Dept. of Mathematics
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1993
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 11
Subjects: GRAPHS; CHROMATICITY; COMPETITION
Other titles: NPS-MA-93-020.
Description: 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. Competition graphs, Graph coloring.
Notes: Cover title.

"NPS-MA-93-020."

"Technical report for period April 1993 - July 1993."

AD A275 520.

Includes bibliographical references (p. 10-11)

aq/  /aq cc:9116 09/12/97