Thesis Defense - Skulrattanakulchai

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.

This work gives 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. It also gives the simplest known linear-time algorithms for 4-edge-coloring and 4-list-edge-coloring subcubic graphs. It also gives the first linear-time algorithms for 5-total-coloring, 5-list-total-coloring, acyclically 4-vertex-coloring, and acyclically 5-edge-coloring subcubic graphs. It also gives the first randomized, linear-work with high probability, EREW PRAM algorithm for 4-edge-coloring and 4-list-edge-coloring subcubic graphs.

The number of colors used in each of the coloring algorithms on subcubic graphs is the least possible with respect to the class of subcubic graphs. In other words, for each problem on subcubic graphs treated herein there exist some subcubic graphs that require as many colors as used by the algorithm. The results of this work are achieved through the use of two main techniques developed by the author.

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.