zbMATH — the first resource for mathematics

The 4-choosability of plane graphs without 4-cycles. (English) Zbl 0931.05036
Summary: A graph \(G\) is called \(k\)-choosable if \(k\) is a number such that if we give lists of \(k\) colors to each vertex of \(G\) there is a vertex coloring of \(G\) where each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosable. \(\copyright\) Academic Press.

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
PDF BibTeX Cite
Full Text: DOI
[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[2] Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 12, 183-186, (1996) · Zbl 0838.05039
[3] Bondy, J.A.; Murty, U.R.S., Graph theory with applications, (1976), Macmillan London · Zbl 1226.05083
[4] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[5] Steinberg, R., The state of the three color problem, Quo vadis: graph theory?, Ann. discrete math., 55, (1993), North-Holland Amsterdam, p. 211-248 · Zbl 0791.05044
[6] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[7] Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[8] Vizing, V.G., Vertex coloring with given colors, Diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303
[9] Voigt, M., List colouring of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[10] Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete math., 146, 325-328, (1995) · Zbl 0843.05034
[11] Voigt, M.; Wirth, B., On 3-colorable non-4-choosable planar graphs, J. graph theory, 24, 233-235, (1997) · Zbl 0868.05025
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.