A special k-coloring for a connected k-chromatic graph

✍ Scribed by Guantao Chen; Richard H. Schelp; Warren E. Shreve

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 293 KB
• Volume: 170
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00123-9

✦ Synopsis

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number x(G) --k can be properly vertex colored by k colors so that for each pair of vertices x0 and x~ in any color class there exist vertices xl, x2 .... , xp_ ~ of the same class with dist(xi, xi+ 1) ~ f(k) for each i, 0 ~< i ~< p -1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance >f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is ~k(k -2) + 1.