tailieunhanh - Báo cáo toán học: "Graph Color Extensions: When Hadwiger’s Conjecture and Embeddings Help"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Graph Color Extensions: When Hadwiger’s Conjecture and Embeddings Help | Graph Color Extensions When Hadwiger s Conjecture and Embeddings Help Michael O. Albertson Department of Mathematics Smith College Northampton MA 01063 USA albertson@ Joan P. Hutchinson Department of Mathematics and Computer Science Macalester College St. Paul MN 55105 USA hutchinson@ Submitted April 29 2002 Accepted September 12 2002. MR Subject Classifications 05C15 05C10 Abstract Suppose G is r-colorable and P c V G is such that the components of G P are far apart. We show that any r s -coloring of G P in which each component is s-colored extends to an r s -coloring of G. If G does not contract to K5 or is planar and s 2 then any r s 1 -coloring of P in which each component is s-colored extends to an r s 1 -coloring of G. This result uses the Four Color Theorem and its equivalence to Hadwiger s Conjecture for k 5. For s 2 this provides an affirmative answer to a question of Thomassen. Similar results hold for coloring arbitrary graphs embedded in both orientable and non-orientable surfaces. 1 Introduction Suppose G is an r-colorable graph and P c V V G . One naturally asks if an r-coloring of G P extends to a t-coloring of G where r t. This question is NP-complete even with severe restrictions on G. Its complexity has been well studied for a survey see 24 . Several years ago Thomassen asked if a planarity assumption and a distance constraint on P would help. Question 1 21 Suppose G is a planar graph and P c V is such that the distance between any two vertices in P is at least 100. Can a 5-coloring of P be extended to a 5-coloring of G THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2002 R37 1 The answer to Thomassen s question is yes but the result does not require any topology- Theorem 1 1 If x G r and 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. If x G r there is no similar extension theorem with r colors even if G is planar and r 4 1 . In response to Theorem 1 .