Paper Info
Title
<p>A relaxation of Novosibirsk 3-color conjecture</p>
Abstract
The famous Steinberg's conjecture states that planar graphs without cycles of lengths 4 and 5 are (0, 0, 0)-colorable. Recently, Cohen-Addad et al. [6] demonstrated that Steinberg's conjecture is false by constructing a counterexample. Let F denote the family of planar graphs without 3-cycles adjacent to cycles of lengths 3 and 5. Borodin et al. posed the Novosibirsk 3-color conjecture, which is the statement that every graph in F is (0, 0, 0)-colorable. It is easy to observe that the counterexample of Cohen-Addad et al. shows also that if G is an element of F, then G is not always (0, 0, 0)-colorable. Motivated by this observation, this paper proves that every member G is an element of & nbsp;F is (1, 1, 0)-colorable, which is a positive step. (C)& nbsp;2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2022
10.1016/j.disc.2021.112762
DISCRETE MATHEMATICS
Keywords
DocType
Volume
Novosibirsk 3-color conjecture, Bad cycles, Superextension, Discharging
Journal
345
Issue
ISSN
Citations 
4
0012-365X
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Ziwen Huang101.69