A relaxation of Steinberg's Conjecture

2012/08/16 by Hill, Owen, Yu, Gexin
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1208.3395

Abstract

A graph is (c₁, c₂, ..., c_k)-colorable if the vertex set can be partitioned into k sets V₁,V₂, ..., V_k, such that for every i: 1≤ i≤ k 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).

Related

• (1,0,0)-colorability of planar graphs without cycles of length 4 or 6
• Steinberg's Conjecture is false
• The proof of Steinberg's three coloring conjecture
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Plane graphs without 4- and 5-cycles and without ext-triangular 7-cycles are 3-colorable