Chromatic numbers of competition graphs
Loading...
Authors
Merz, Sarah K.
Rasmussen, Craig W.
Lundgren, J. Richard
Subjects
Advisors
Date of Issue
1993
Date
1993
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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.
Type
Technical Report
Description
Series/Report No
Department
Mathematics
Organization
Applied Mathematics (MA)
Graduate School of Engineering and Applied Science (GSEAS)
Identifiers
NPS Report Number
NPS-MA-93-020
Sponsors
Funder
Format
11 p.: ill. ; 28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.