Defective 2-colorings of sparse graphs

A graph G   is (j,k)(j,k)-colorable if its vertices can be partitioned into subsets V1V1 and V2V2 such that every vertex in G[V1]G[V1] has degree at most j   and every vertex in G[V2]G[V2] has degree at most k  . We prove that if k⩾2j+2k⩾2j+2, then every graph with maximum average degree at most 2(2−k+2(j+2)(k+1)) is (j,k)(j,k)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close to 2(2−k+2(j+2)(k+1)) (from above) that are not (j,k)(j,k)-colorable.In fact, we prove a stronger result by establishing the best possible sufficient condition for the (j,k)(j,k)-colorability of a graph G   in terms of the minimum, φj,k(G)φj,k(G), of the difference φj,k(W,G)=(2−k+2(j+2)(k+1))|W|−|E(G[W])| over all subsets W   of V(G)V(G). Namely, every graph G   with φj,k(G)>−1k+1 is (j,k)(j,k)-colorable. On the other hand, we construct infinitely many non-(j,k)(j,k)-colorable graphs G   with φj,k(G)=−1k+1.