# 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.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
##### Keywords:
faces; choosabiilty; triangle; vertex coloring; plane graph; 4-cycles
Full Text:
##### References:
  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049  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  Bondy, J.A.; Murty, U.R.S., Graph theory with applications, (1976), Macmillan London · Zbl 1226.05083  Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)  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  Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023  Thomassen, C., 3-List-coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029  Vizing, V.G., Vertex coloring with given colors, Diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303  Voigt, M., List colouring of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030  Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete math., 146, 325-328, (1995) · Zbl 0843.05034  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.