Efficient Graph Coloring Algorithms via Bottom-up Ordering & Subcubic Graph Structure

San Skulrattanakulchai, Ph.D.
University of Colorado at Boulder

January 31, 2003
11 a.m. - 12 noon
Fuller Labs 320

Abstract

A proper coloring of a graph is a partition of its elements in such a way that no two adjacent or incident elements belong to the same set in the partition. It is a vertex coloring, an edge coloring, or a total coloring, according as the elements to be partitioned are the vertices alone, the edges alone, or both the vertices and edges, respectively. A list coloring is a proper coloring subject to an extra condition that a color to be assigned to an element must come from that element's set ("list") of colors priorly associated with that element as part of the input. A proper vertex (or edge) coloring is acyclic if there is no 2-colored cycle. A subcubic graph is a graph having maximum degree not exceeding three. Subcubic graphs are important and interesting both theoretically and in practice.

Graph Coloring is a central subject in combinatorics. Its importance in computer science is due to the fact that numerous naturally occurring optimization problems can be modeled as graph coloring problems. However, computing the least number of colors needed in a proper vertex coloring, edge coloring, or total coloring in general graphs is known to be NP-hard.

We introduce two techniques for designing efficient approximation graph coloring algorithms. The first technique is a method of ordering the vertices and edges of a graph so that a semi-greedy algorithm can be used to color them. The second technique is a simple principle for decomposing subcubic graphs into two simpler subgraphs. Solving a subcubic graph problem then amounts to solving a subproblem on each subgraph and combining the two solutions into a solution to the original problem.

Using these techniques, we obtain the first linear-time algorithm to list- vertex-color, whenever possible, any graph every vertex of which has at least as many colors in its list as the maximum degree of the graph. We also obtain simple linear-time algorithms for 4-edge-coloring and 4-list-edge-coloring subcubic graphs. We also obtain the first linear-time algorithms for 5-total- coloring, 5-list-total-coloring, acyclically 4-vertex-coloring, and acyclically 5-edge-coloring subcubic graphs. We also obtain the first randomized, linear- work with high probability, EREW PRAM algorithm for 4-edge-coloring and 4-list- edge-coloring subcubic graphs.

In this talk, I will describe these techniques and present some sample algorithms derived from them.

Host

Prof. Micha Hofri

Refreshments will be served in FL 320 beginning at 10:50 a.m.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT