zbMATH — the first resource for mathematics

Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable. (English) Zbl 1309.05058
Summary: Let \(d_1, d_2,\dots ,d_k\) be \(k\) non-negative integers. A graph \(G\) is \((d_1,d_2,\dots,d_k)\)-colorable, if the vertex set of \(G\) can be partitioned into subsets \(V_1,V_2,\dots,V_k\) such that the subgraph \(G[V_i]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i=1,2,\dots,k\). Let \(\digamma \) be the family of planar graphs with cycles of length neither 4 nor 5. Steinberg conjectured that every graph of \(\digamma \) is \((0,0,0)\)-colorable. In this paper, we prove that every graph of \(\digamma\) is \((1,1,0)\)-colorable.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Cowen, LJ; Cowen, RH; Woodall, DR, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J Graph Theory, 10, 187-195, (1986) · Zbl 0596.05024
[2] Eaton, N; Hull, T, Defective List colorings of planar graphs, Bull Inst Combinatorics Appl, 25, 79-87, (1999) · Zbl 0916.05026
[3] S̆krekovski R, (1999) List improper coloring of planar graphs. Combinatorics Probab Comput 8:293-299 · Zbl 0596.05024
[4] Steinberg, R, The state of the three color problem. quo vadis, graph theory?, Ann Discret Math, 55, 211-248, (1993)
[5] Xu, B, On (3; 1)-coloring of plane graphs, SIAM J Discret Math, 23, 205-220, (2009) · Zbl 1221.05167
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.