A graph G is
$$(d_{1},d_{2},\ldots ,d_{k})$$
-colorable if the vertex set of G can be partitioned into subsets
$$V_{1}, V_{2},\ldots , V_{k}$$
such that the subgraph
$$G[V_{i}]$$
induced by
$$V_{i}$$
has maximum degree at most
$$d_{i}$$
for
$$i = 1, 2, \ldots , 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) as...
