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)

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: DOI
[1] 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
[2] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049
[3] Alon, N.; Tuza, Z.; Voigt, M., Choosability and fractional chromatic numbers, Discrete math., 165-166, 31-38, (1997) · Zbl 0877.05020
[4] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan New York · Zbl 1134.05001
[5] 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
[6] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[7] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory, ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[8] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 119-130, (1996) · Zbl 0865.05066
[9] S. Gutner, and, M. Tarsi, Some results on (a, b)-choosability, to appear. · Zbl 1198.05049
[10] 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
[11] Peter, C. B. Lam, B. Xu, and, J. Liu, On 3-choosability of some plane graphs of girth 4, preprint.
[12] Steinberg, R., The state of the three color problem, (), 211-248 · Zbl 0791.05044
[13] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory, ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[14] Thomassen, C., 3-List-coloring planar graph of girth 5, J. combin. theory, ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[15] Tuza, Z.; Voigt, M., Every 2-choosable graph is (2m, m)-choosable, J. graph theory, 22, 245-252, (1996) · Zbl 0853.05034
[16] Tuza, Z.; Voigt, M., On a conjecture of erdős, Rubin and Taylor, Tatra mt. math. publ., 9, 69-82, (1996)
[17] Vizing, V.G., Vertex coloring with a given colors, Diskret. anal., 29, 3-10, (1976) · Zbl 1249.90303
[18] 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.