A Relaxation of Steinberg's Conjecture

DOI10.1137/120888752zbMATH Open1268.05074arXiv1208.3395OpenAlexW2031630984WikidataQ122902541 ScholiaQ122902541MaRDI QIDQ5300514FDOQ5300514

Gexin Yu, Owen Hill

Publication date: 27 June 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: A graph is $(c_1,c_2,\mathrm{...},c_k)$-colorable if the vertex set can be partitioned into $k$ sets $V_1,V_2,\mathrm{...},V_k$, such that for every $i:1leqileqk$ the subgraph $G[V_i]$ has maximum degree at most $c_i$. We show that every planar graph without 4- and 5-cycles is $(1,1,0)$-colorable and $(3,0,0)$-colorable. This is a relaxation of the Steinberg Conjecture that every planar graph without 4- and 5-cycles are properly 3-colorable (i.e., $(0,0,0)$-colorable).

Full work available at URL: https://arxiv.org/abs/1208.3395

zbMATH Keywords

planar graphsSteinberg's conjecturerelaxed coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cited In (14)

• A relaxation of the strong Bordeaux Conjecture
• A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable
• Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable
• A relaxation of the Bordeaux conjecture
• A relaxation of Novosibirsk 3-color conjecture
• \((1,0,0)\)-colorability of planar graphs without prescribed short cycles
• Every planar graph without 3-cycles adjacent to 4-cycles and without 6-cycles is (1, 1, 0)-colorable
• \((1,0,0)\)-colorability of planar graphs without cycles of length \(4\) or \(6\)
• Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable
• Improper colorability of planar graphs without prescribed short cycles
• \((1,0,0)\)-colorability of planar graphs without cycles of length 4, 5 or 9

This page was built for publication: A Relaxation of Steinberg's Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300514)