Search

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]