Skip to Main content Skip to Navigation

Steinberg's Conjecture and near-colorings

Abstract : Let F be the family of planar graphs without cycles of length 4 and 5. Steinberg's Conjecture (1976) that says every graph of F is 3-colorable remains widely open. Focusing on a relaxation proposed by Erd˝os (1991), many studies proved the conjecture for some subfamilies of F. For example, Borodin et al. proved that every planar graph without cycles of length 4 to 7 is 3- colorable. In this note we propose to relax the problem not on the family of graphs but on the coloring by considering near-colorings. A graph G = (V,E) is said to be (i, j, k)-colorable if its vertex set can be partitioned into three sets V1, V2, V3 such that the graphs G[V1],G[V2],G[V3] induced by the sets V1, V2, V3 have maximum degree at most i, j, k respectively. Under this terminology, Steinberg's Conjecture says that every graph of F is (0, 0, 0)-colorable. A result of Xu (2008) implies that every graph of F is (1, 1, 1)-colorable. Here we prove that every graph of F is (2, 1, 0)-colorable and (4, 0, 0)-colorable.
Document type :
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download
Contributor : Frederic Havet <>
Submitted on : Monday, July 4, 2011 - 2:09:12 PM
Last modification on : Monday, October 12, 2020 - 10:30:12 AM
Long-term archiving on: : Wednesday, October 5, 2011 - 2:23:08 AM


Files produced by the author(s)


  • HAL Id : inria-00605810, version 1


Gerard Chang, Frédéric Havet, Mickael Montassier, André Raspaud. Steinberg's Conjecture and near-colorings. [Research Report] RR-7669, INRIA. 2011. ⟨inria-00605810⟩



Record views


Files downloads