Accession Number:

ADA275520

Title:

Chromatic Numbers of Competition Graphs

Descriptive Note:

Technical rept. Apr-Jul 1993

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS

Report Date:

1993-10-14

Pagination or Media Count:

16.0

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 CG 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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE