Back to Search
Start Over
Planar Graphs Without Adjacent Cycles of Length at Most Five are (2, 0, 0)-Colorable.
- Source :
- Bulletin of the Malaysian Mathematical Sciences Society; May2021, Vol. 44 Issue 3, p1167-1194, 28p
- Publication Year :
- 2021
-
Abstract
- A graph G is (d 1 , d 2 , ... , d k) -colorable if the vertex set of G can be partitioned into subsets V 1 , V 2 , ... , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , ... , k . Novosibirsk's Conjecture (Sib lektron Mat Izv 3:428–440, 2006) says that every planar graph without 3-cycles adjacent to cycles of length 3 or 5 is 3-colorable. Borodin et al. (Discrete Math 310: 167–173, 2010) asked whether every planar graph without adjacent cycles of length at most 5 is 3-colorable. Cohen-Addad et al. (J Comb Theory Ser B 122:452–456, 2017) gave a negative answer to both Novosibirsk's conjecture and Borodin et al.'s problem. Zhang et al. (Discrete Math 339:3032–3042, 2016) asked whether every planar graph without adjacent cycles of length at most 5 is (1, 0, 0)-colorable. In this paper, we show that every planar graph without adjacent cycles of length at most five is (2, 0, 0)-colorable, which improves the result of Chen et al. (Discrete Math 339:886–905, 2016) who proved that every planar graph without cycles of length 4 and 5 is (2, 0, 0)-colorable. [ABSTRACT FROM AUTHOR]
- Subjects :
- PLANAR graphs
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 01266705
- Volume :
- 44
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Bulletin of the Malaysian Mathematical Sciences Society
- Publication Type :
- Academic Journal
- Accession number :
- 149671959
- Full Text :
- https://doi.org/10.1007/s40840-020-01004-8