## Abstract

A graph G is (j, k)-colorable if its vertices can be partitioned into subsets V_{1} and V_{2} such that every vertex in G[V_{1}] has degree at most j and every vertex in G[V_{2}] has degree at most k. We prove that if k≥2j+2, then every graph with maximum average degree at most 2(2-k+2(j+2)(k+1)) is (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)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (j, k)-colorability of a graph G in terms of the minimum, φ_{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). Namely, every graph G with φj,k(G)>-1k+1 is (j, k)-colorable. On the other hand, we construct infinitely many non-(j, k)-colorable graphs G with φj,k(G)=-1k+1.

Original language | English (US) |
---|---|

Pages (from-to) | 72-80 |

Number of pages | 9 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 104 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2014 |

## Keywords

- Defective coloring
- Improper coloring
- Maximum average degree

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics