Abstract
Let G be a planar graph and W be a subgraph whose each component is a \(K_{2}\) of G. Let d be the minimum distance between any two distinct components of W. It is known that, if \(d\ge 8\), then any 5-coloring of W can be extended to a 5-coloring of G. Up to now, it is the best possible with respect to the distance constraint. In this paper, we obtain sufficient conditions for such coloring extension when \(d\ge 4\), \(d\ge 6\) and \(d\ge 7\). It partially answers Albertson’s question in Albertson (1998). Then we extend a certain 3-coloring of some disjoint cycles that are face boundaries to a 5-coloring of the entire graph.
Similar content being viewed by others
References
Albertson, M.O.: You can’t paint yourself into a corner. J. Combin. Theory Ser. B 73, 189–194 (1998)
Albertson, M.O., Moore, E.H.: Extending graph colorings. J. Combin. Theory Ser. B 77, 83–95 (1999)
Albertson, M.O., Hutchinson, J.P.: Graph color extensions: when Hadwiger’s conjecture and embedding helps, Electron. J. Combin., 9 (2002) R37(10 p)
Ballantine, J.P.: A postulational introduction to the four color problem, Publ. in Math., Vol. 2, pp. 1-16, Univ. of Washington, Seattle, (1930)
Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)
Brewster, R.C., Noel, J.A.: Extending precolorings of circular cliques. Discrete Math. 312, 35–41 (2012)
Levow, R.B.: Coloring planar graphs with five or more colors. In: Proceedings of 5th S.-E. Conference on Combinatorics, Graph theory, and Computing, Utilitas Math. Publ., Winnepeg, pp. 549-561(1974)
Thomassen, C.: Five-coloring maps on surfaces. J. Combin. Theory Ser. B 59, 89–105 (1993)
Thomassen, C.: Color-critical graphs on a fixed surface. J. Combin. Theory Ser. B 70, 67–100 (1997)
Tuza, Z.: Graph colorings with local constraints-a survey. Discuss. Math. Graph Theory 17, 161–228 (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by Science and Technology Commission of Shanghai Municipality under Grant No.13dz2260400.
Rights and permissions
About this article
Cite this article
Lu, W., Ren, H. Extending Colorings of Planar Graphs. Graphs and Combinatorics 35, 1161–1167 (2019). https://doi.org/10.1007/s00373-019-02067-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-019-02067-6