TY - JOUR

T1 - On 1-improper 2-coloring of sparse graphs

AU - Borodin, O. V.

AU - Kostochka, A.

AU - Yancey, M.

N1 - Funding Information:
The research of the second author was supported in part by NSF grant DMS-0965587 and by the Ministry of Education and Science of the Russian Federation (Contract No. 14.740.11.0868 ).
Funding Information:
The research of the third author was partially supported by the Arnold O. Beckman Research Award of the University of Illinois at Urbana-Champaign.
Funding Information:
The research of the first author was supported in part by grants 08-01-00673 and 09-01-00244 of the Russian Foundation for Basic Research .

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Improper coloring

KW - Maximum average degree

KW - Planar graph

KW - Sparse graph

UR - http://www.scopus.com/inward/record.url?scp=84883200671&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883200671&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2013.07.014

DO - 10.1016/j.disc.2013.07.014

M3 - Article

AN - SCOPUS:84883200671

SN - 0012-365X

VL - 313

SP - 2638

EP - 2649

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 22

ER -