Accession Number : ADA333454

Title :   Approximating the Chromatic Number of an Arbitrary Graph Using a Supergraph Heuristic

Descriptive Note : Master's thesis

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Eggen, Loren G.

PDF Url : ADA333454

Report Date : JUN 1997

Pagination or Media Count : 76

Abstract : We color the vertices of a graph G, so that no two adjacent vertices have the same color. We would like to do this as cheaply as possible. An efficient coloring would be very helpful in optimization models, with applications to bin packing, examination timetable construction, and resource allocations, among others. Graph coloring with the minimum number of colors is in general an NP-complete problem. However, there are several classes of graphs for which coloring is a polynomial-time problem. One such class is the chordal graphs. This thesis deals with an experimental algorithm to approximate the chromatic number of an input graph G. We first find a maximal edge-induced chordal subgraph H of G. We then use a completion procedure to add edges to H, so that the chordality is maintained, until the missing edges from G are restored to create a chordal supergraph S. The supergraph S can then be colored using the greedy approach in polynomial time. The graph G now inherits the coloring of the supergraph S.

Descriptors :   *GRAPHS, *HEURISTIC METHODS, ALGORITHMS, OPTIMIZATION, THESES, APPLIED MATHEMATICS, SET THEORY, SEQUENCES(MATHEMATICS).

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE