zbMATH — the first resource for mathematics

Colouring planar graphs with three colours and no large monochromatic components. (English) Zbl 1334.05030
The main result of the paper proves the existence of a function \(f :\mathbb{N} \to \mathbb{N}\) such that the vertices of every planar graph with maximum degree \(\Delta\) can be 3-coloured in such a way that each monochromatic component has at most \(f(\Delta)\) vertices. This is best possible (the number of colours cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by J. Kleinberg et al. in [“Storage management for evolving databases”, in: Proceedings of the 38th annual IEEE symposium on foundations of computer science (FOCS 1997), October 20–22, 1997, Miami Beach, Florida. Los Alamitos, CA: IEEE Computer Society. 353–362 (1997; doi:10.1109/SFCS.1997.646124)].
The result can be extended to a higher genus which improves a special case of the result of N. Alon et al. [J. Comb. Theory, Ser. B 87, No. 2, 231–243 (2003; Zbl 1023.05045)].

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
Full Text: DOI arXiv
[1] Combin. Probab. Comput. 17 pp 577– (2008)
[2] DOI: 10.1007/BF02579141 · Zbl 0555.05030 · doi:10.1007/BF02579141
[3] DOI: 10.1016/j.jctb.2012.03.001 · Zbl 1244.05075 · doi:10.1016/j.jctb.2012.03.001
[4] DOI: 10.1016/j.jctb.2006.11.002 · Zbl 1123.05039 · doi:10.1016/j.jctb.2006.11.002
[5] DOI: 10.1016/S0095-8956(03)00031-5 · Zbl 1033.05083 · doi:10.1016/S0095-8956(03)00031-5
[6] DOI: 10.1007/BF01303516 · Zbl 0790.05067 · doi:10.1007/BF01303516
[7] DOI: 10.1016/S0095-8956(02)00006-0 · Zbl 1023.05045 · doi:10.1016/S0095-8956(02)00006-0
[8] DOI: 10.1016/j.ejc.2010.05.015 · Zbl 1215.05177 · doi:10.1016/j.ejc.2010.05.015
[9] DOI: 10.1017/S0305004100061521 · Zbl 0551.05047 · doi:10.1017/S0305004100061521
[10] Graphs on Surfaces (2001)
[11] Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 8 pp 109– (1959)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.