Coloring Algorithms on Subcubic Graphs

We present e cient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The rst algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears

to be simpler than previous ones. The second algorithm is the rst randomized EREW PRAM algorithm for the same problem. It uses O(n= log n) processors and runs in O(log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the rst linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the rst linear-time algorithm to 5-list-total- color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs. Keywords: List Edge Coloring, Total Coloring, List Total Coloring, Subcubic Graphs 1. Introduction We present e cient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The problems we attack are by now well-studied generalizations of standard vertex and edge coloring [19]. The rst algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the rst randomized EREW PRAM algorithm for the...

Website: homepages.gac.edu | Filesize: -
No of Page(s): 20
Download Coloring Algorithms on Subcubic Graphs∗ and 1. Introduction We ....pdf