# zbMATH — the first resource for mathematics

On structure of some plane graphs with application to choosability. (English) Zbl 1024.05049
Summary: A graph $$G=(V, E)$$ is $$(x, y)$$-choosable for integers $$x> y\geq 1$$ if for any given family $$\{A(v)\mid v\in V\}$$ of sets $$A(v)$$ of cardinality $$x$$, there exists a collection $$\{B(v)\mid v\in V\}$$ of subsets $$B(v)\subset A(v)$$ of cardinality $$y$$ such that $$B(u)\cap B(v)= \varnothing$$ whenever $$uv\in E(G)$$. In this paper, structures of some plane graphs, including plane graphs with minimum degree 4, are studied. Using these results, we may show that if $$G$$ is free of $$k$$-cycles for some $$k\in \{3,4, 5,6\}$$, or if any two triangles in $$G$$ have distance at least 2, then $$G$$ is $$(4m, m)$$-choosable for all nonnegative integers $$m$$. When $$m= 1$$, $$(4m, m)$$-choosable is simply 4-choosable. So these conditions are also sufficient for a plane graph to be 4-choosable.
Reviewer: Reviewer (Berlin)

##### MSC:
 05C38 Paths and cycles 05C10 Planar graphs; geometric and topological aspects of graph theory 05C75 Structural characterization of families of graphs
cycle; triangle
Full Text:
##### References:
  Alon, N., Restricted colorings of graphs, Surveys in combinatorics 1993, London mathematics society lecture notes series, 187, (1993), Cambridge Univ. Press Cambridge, p. 1-33 · Zbl 0791.05034  Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049  Alon, N.; Tuza, Z.; Voigt, M., Choosability and fractional chromatic numbers, Discrete math., 165-166, 31-38, (1997) · Zbl 0877.05020  Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan New York · Zbl 1134.05001  Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 21, 183-186, (1996) · Zbl 0838.05039  Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)  Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory, ser. B, 63, 153-158, (1995) · Zbl 0826.05026  Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 119-130, (1996) · Zbl 0865.05066  S. Gutner, and, M. Tarsi, Some results on (a, b)-choosability, to appear. · Zbl 1198.05049  Lam, Peter C.B.; Xu, B.; Liu, J., The 4-choosability of plane graphs without 4-cycles, J. combin. theory, ser. B, 76, 117-126, (1999) · Zbl 0931.05036  Peter, C. B. Lam, B. Xu, and, J. Liu, On 3-choosability of some plane graphs of girth 4, preprint.  Steinberg, R., The state of the three color problem, (), 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 graph of girth 5, J. combin. theory, ser. B, 64, 101-107, (1995) · Zbl 0822.05029  Tuza, Z.; Voigt, M., Every 2-choosable graph is (2m, m)-choosable, J. graph theory, 22, 245-252, (1996) · Zbl 0853.05034  Tuza, Z.; Voigt, M., On a conjecture of erdős, Rubin and Taylor, Tatra mt. math. publ., 9, 69-82, (1996)  Vizing, V.G., Vertex coloring with a given colors, Diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303  Voigt, M.; Wirth, B., On 3-colorable non-4-choosable planar graph, 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.