Approximating the chromatic number of an arbitrary graph using a supergraph heuristic
Contributors: Naval Postgraduate School (U.S.) 
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1997
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 57
Subjects: GRAPHS; HEURISTIC METHODS
Description: 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.
Notes: Thesis advisor, Craig W. Rasmussen.

AD-A333 454.

Thesis (M.S. in Applied Mathematics) Naval Postgraduate School, June 1997.

Includes bibliographical references (p. 55-56)

dk/dk cc:9116 02/03/98.