Back to Search
Start Over
A relaxation of Novosibirsk 3-color conjecture.
- Source :
-
Discrete Mathematics . Apr2022, Vol. 345 Issue 4, pN.PAG-N.PAG. 1p. - Publication Year :
- 2022
-
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 ∈ F , then G is not always (0 , 0 , 0) -colorable. Motivated by this observation, this paper proves that every member G ∈ F is (1 , 1 , 0) -colorable, which is a positive step. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 345
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 155149359
- Full Text :
- https://doi.org/10.1016/j.disc.2021.112762