A relaxation of Steinberg's conjecture

DOI10.1137/120888752MaRDI QIDQ5300514zbMATH OpenOpenAlexWikidataFDO

Authors Owen Hill, Gexin Yu

Publication date 27 June 2013

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

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

zbMATH Keywords

planar graphsrelaxed coloringSteinberg's conjecture

Mathematics Subject Classification ID

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

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).

Recommendations

• Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
• (\(1,1,0\))-coloring of planar graphs without cycles of length 4 and 6
• Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable

Cited in

(21)

• 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\)
• A relaxation of Novosibirsk 3-color conjecture
• New restrictions on defective coloring with applications to Steinberg-type graphs
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• A relaxation of the Bordeaux conjecture
• A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
• 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
• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
• A relaxation of the strong Bordeaux Conjecture
• \((1,0,0)\)-colorability of planar graphs without prescribed short cycles
• Planar graphs without cycles of length 4 or 5 are (7 : 2)-colorable
• On the strong Bordeaux conjecture
• An \((\mathcal{F}_2, \mathcal{F}_6)\)-partition of planar graphs without cycles of length 4 and 6
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• The independence ratio of 4-cycle-free planar graphs
• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
• Planar graphs without cycles of length 4 or 5 are (2, 0, 0)-colorable

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)