Chromatic Numbers of Competition Graphs

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 14, 1993
Accession Number
ADA275520

Entities

People

  • Craig W. Rasmussen
  • J. R. Lundgren
  • Sarah K. Merz

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Acquisition
  • Algorithms
  • Classification
  • Competition
  • Continents
  • Contracts
  • Elimination
  • Geographic Regions
  • Geometry
  • Inequalities
  • Intervals
  • Mathematics
  • Military Research
  • Notation
  • Schools
  • Security
  • Triangles

Readers

  • Economics
  • Graph Algorithms and Convex Optimization.