On 1 -improper 2 -coloring of sparse graphs
2013; Elsevier BV; Volume: 313; Issue: 22 Linguagem: Inglês
10.1016/j.disc.2013.07.014
ISSN1872-681X
AutoresO.V. Borodin, Alexandr Kostochka, Matthew Yancey,
Tópico(s)Graph Labeling and Dimension Problems
ResumoA 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.
Referência(s)