Extending Graph Colorings

✍ Scribed by Michael O Albertson; Emily H Moore

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 172 KB
• Volume: 77
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1999.1913

✦ Synopsis

Suppose /(G)=r and P V(G). It is known that if the distance between any two vertices in P is at least 4, then any (r+1)-coloring of P extends to an (r+1)-coloring of all of G, but an r-coloring of P might not extend to an r-coloring of G. We show that if the distance between any two vertices in P is at least 3, then an (r+1)coloring of P can be extended to a W(3r+1)Â2X-coloring of G. Kostochka showed that if P induces a set of k-cliques whose pairwise distance is at least 4k, then an (r+1)-coloring of P can be extended to an (r+1)-coloring of G. We give Kostochka's proof and more precise results concerning the distance required between precolored components. For example, we show that when k=r, there is a coloring extension provided the cliques have pairwise distance at least 3k. We relate the structure of the precolored components to the number of extra colors needed in a coloring extension theorem. We construct families of graphs to show that all of the above results are close to being best possible.