A rainbow about T-colorings for complete graphs

✍ Scribed by Klaus Jansen

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 700 KB
• Volume: 154
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00344-i

✦ Synopsis

Given a finite set T of positive integers, with 0 E T, a T-coloring of a graph G = (V, E) is a functionf: V -+ No such that for each {x, y} E E If(x) -f(y)l#T. The T-span is the difference between the largest and smallest colors and the T-span of G is the minimum span over all T-colorings of G. We show that the problem to find the T-span for a complete graph is NP-complete. ~PT,Y(G) = xmy; If(x) -Al, and the T-span ofG is the minimum span of a T-coloring of G, denoted by sp, (G). If T = {0}, then the T-coloring is the same as an ordinary coloring. In this case, spT(G) = x(G) -1 where x(G) is the chromatic number of G. Therefore, the problem to find sp,(G) in general is NP-complete.

We study the problem to find sp, (K,) for a complete graph K, with n vertices. The simplest algorithm for a complete graph is the greedy algorithm. In each step, the smallest possible color that will not violate the definition of a T-coloring is chosen.