On 1-improper 2-coloring of sparse graphs

O. V. Borodin, A. Kostochka, M. Yancey

Research output: Contribution to journalArticlepeer-review


A graph G is (1,1)-colorable if its vertices can be partitioned into subsets V1 and V2 such that every vertex in G[ Vi] has degree at most 1 for each iâ̂̂{1,2}. We prove that every graph with maximum average degree at most 145 is (1,1)-colorable. In particular, it follows that every planar graph with girth at least 7 is (1,1)-colorable. On the other hand, we construct graphs with maximum average degree arbitrarily close to 145 (from above) that are not (1,1)-colorable. In fact, we establish the best possible sufficient condition for the (1,1)-colorability of a graph G in terms of the minimum, ρG, of ρG(S)=7|S|-5|E(G[S])| over all subsets S of V(G). Namely, every graph G with ρG≥0 is (1,1)-colorable. On the other hand, we construct infinitely many non-(1,1)-colorable graphs G with ρG=- 1. This solves a related conjecture of Kurek and Ruciński from 1994.

Original languageEnglish (US)
Pages (from-to)2638-2649
Number of pages12
JournalDiscrete Mathematics
Issue number22
StatePublished - 2013


  • Improper coloring
  • Maximum average degree
  • Planar graph
  • Sparse graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On 1-improper 2-coloring of sparse graphs'. Together they form a unique fingerprint.

Cite this