Department of Computer Science University of Colorado Boulder
 cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
 home | quick links | site map | who's where | cs a-z
home · events · thesis defenses · 2002-2003 ·

Thesis Defense - Skulrattanakulchai

11/19/2002
5:00pm-7:00pm
ECOT 832

Efficient Algorithms for Graph Coloring: Vertex, Edge, List, Total, and Acyclic Coloring
Computer Science PhD Candidate

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.

 Committee: Harold (Hal) Gabow, Professor (Chair) Andrzej Ehrenfeucht, Professor Michael Main, Associate Professor Michael Eisenberg, Associate Professor Don Monk, Department of Mathematics

 Department of Computer Science College of Engineering and Applied Science University of Colorado Boulder Boulder, CO 80309-0430 USA Questions/Comments? Send email to webmaster at cs.colorado.edu Engineering Center Office Tower ECOT 717 +1-303-492-7514 FAX +1-303-492-2844
 XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado Privacy · Legal · Trademarks May 5, 2012 (13:40)

.