zbMATH — the first resource for mathematics

Planar graphs are 1-relaxed, 4-choosable. (English) Zbl 1221.05077
Summary: We show that every planar graph \(G=(V,E)\) is 1-relaxed, 4-choosable. This means that, for every list assignment \(L\) that assigns a set of at least four colors to each vertex, there exists a coloring \(f\) such that \(f(v)\in L(v)\) for every vertex \(v\in V\) and each color class \(f^{ - 1}(\alpha )\) of \(f\) induces a subgraph with maximum degree at most 1.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Cowen, L.J.; Cowen, R.H.; Woodall, D.R., Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. graph theory, 10, 2, 187-195, (1986) · Zbl 0596.05024
[2] Eaton, Nancy; Hull, Thomas, Defective List colorings of planar graphs, Bull. inst. combin. appl., 25, 79-87, (1999) · Zbl 0916.05026
[3] Paul Erdős, Arthur L. Rubin, Herbert Taylor, Choosability in graphs, In: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, CA, 1979), in: Congress. Numer. vol. XXVI, Winnipeg, Man, 1980, pp. 125-157. Utilitas Math · Zbl 0469.05032
[4] Škrekovski, R., List improper colourings of planar graphs, Combin. probab. comput., 8, 3, 293-299, (1999) · Zbl 0940.05031
[5] Thomassen, Carsten, Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 1, 180-181, (1994) · Zbl 0805.05023
[6] Vizing, V.G., Coloring the vertices of a graph in prescribed colors (in Russian), Diskret. analiz, no. 29, metody diskret. anal. v teorii kodov i shem, 101, 3-10, (1976)
[7] Voigt, Margit, List colourings of planar graphs, Discrete math., 120, 1-3, 215-219, (1993) · Zbl 0790.05030
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.