zbMATH — the first resource for mathematics

Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable. (English) Zbl 1180.05035
Authors’ summary: “It is known that not all planar graphs are 4-choosable; neither all of them are vertex 2-arborable. However, planar graphs without 4-cycles and even those without 4-cycles adjacent to 3-cycles are known to be 4-choosable. We extend this last result in terms of covering the vertices of a graph by induced subgraphs of variable degeneracy. In particular, we prove that every planar graph without 4-cycles adjacent to 3-cycles can be covered by two induced forests.”

05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Appel, The existence of unavoidable sets of geographically good configurations, Illinois J Math 20 pp 218– (1976) · Zbl 0322.05141
[2] Bollobás, Optimal vertex partition, Bull London Math Soc 11 pp 113– (1979)
[3] Borodin, On decomposition of graphs into degenerate subgraphs (in Russian), Metody Discret Anal 28 pp 3– (1976) · Zbl 0425.05058
[4] O. V. Borodin, Criterion of chromaticity of a degree prescription (in Russian), Abstracts of IV All-Union Conference on Theoretical Cybernetics, Novosibirsk, 1977, pp.127-128.
[5] O. V. Borodin, Problems of colouring and of covering the vertex set of a graph by induced subgraphs (in Russian), Ph.D. Thesis, Novosibirsk, 1979.
[6] Borodin, Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J Graph Theory 21 pp 183– (1996) · Zbl 0838.05039
[7] Borodin, Variable degeneracy: extensions of Brooks’ and Gallai’s theorems, Discrete Math 214 pp 101– (2000) · Zbl 0949.05029
[8] Borodin, Minumum height of edges in C4 -free planar graphs, J Graph Theory 60 (1) pp 80– (2009)
[9] Borodin, Planar graphs without triangular 4-cycles are 4-choosable, Siberian Electronic Math 5 pp 75– (2008) · Zbl 1299.05116
[10] Brooks, On coloring the nodes of a network, Proc Cambridge Math Soc 37 pp 194– (1941) · Zbl 0027.26403
[11] Vizing, Coloring the vertices of a graph with assigned colors, Diskret Anal Novosibirsk 29 pp 3– (1976)
[12] Chartrand, The point arboricity of planar graphs, J London Math Soc 44 pp 612– (1969) · Zbl 0175.50505
[13] Erdös, Choosability in graphs, Congr Numer 26 pp 125– (1979)
[14] He, Edge-partitions of planar graphs and their game coloring numbers, J Graph Theory 41 pp 307– (2002) · Zbl 1016.05033
[15] Gallai, Kritische Graphen I, Publ Math Inst Hungar Acad Sci 8 pp 165– (1963)
[16] Jensen, Graph Coloring Problems (1995)
[17] Kronk, Critical point-arboritic graphs, J London Math Soc 9 pp 459– (1975) · Zbl 0298.05132
[18] Lam, The 4-choosability of plane graphs without 4-cycles, J Combin Theory B 76 pp 117– (1999) · Zbl 0931.05036
[19] Lick, The point partition numbers of closed 2 -manifolds, J London Math Soc 4 pp 577– (1972) · Zbl 0233.05101
[20] Mitchem, An extension of Brooks’ theorem to n-degenerate graphs, Discrete Math 17 pp 291– (1977) · Zbl 0351.05124
[21] Voigt, List colourings of planar graphs, Discrete Math 120 pp 215– (1993) · Zbl 0790.05030
[22] Wegner, Note on a paper by B.Grunbaum on acyclic colorings, Israel J Math 14 pp 409– (1973)
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.