ALCOMFT-TR-02-117

J. D\'\iaz, J. Ne\v set\v ril, M. Serna and D.M. Thilikos
H-colorings of Large Degree Graphs
Barcelona. Work package 4. May 2002.

Abstract: We consider the H-coloring problem on graphs with vertices of large degree. We prove that for H an odd cycle, the problem belongs to P. We also study the phase transition of the problem, for an infinite family of graphs of a given chromatic number, i.e. the threshold density value for which the problem changes from P to NP-complete. We extend the result for the case that the input graph has a logarithmic size of small degree vertices.As a corollary, we get a new result on the chromatic number; a new family of graphs, for which computing the chromatic number can be done in polynomial time.

Postscript file: ALCOMFT-TR-02-117.ps.gz (63 kb).