TY - JOUR

T1 - Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

AU - Borodin, O. V.

AU - Kostochka, A. V.

N1 - Publisher Copyright:
© 2011 Borodin O. V. and Kostochka A. V.

PY - 2011

Y1 - 2011

N2 - A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V1and V0so that in G[V1] every vertex has degree at most 1, while G[V0] is edgeless. We prove that every graph with maximum average degree at most 12/5 is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to 12/5 which are not (1, 0)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V (A)| − 5|E(A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.

AB - A graph G is (1, 0)-colorable if its vertex set can be partitioned into subsets V1and V0so that in G[V1] every vertex has degree at most 1, while G[V0] is edgeless. We prove that every graph with maximum average degree at most 12/5 is (1, 0)-colorable. In particular, every planar graph with girth at least 12 is (1, 0)-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to 12/5 which are not (1, 0)-colorable. In fact, we prove a stronger result by establishing the best possible sufficient condition for the (1, 0)-colorability of a graph G in terms of the minimum, Ms(G), of 6|V (A)| − 5|E(A)| over all subgraphs A of G. Namely, every graph G with Ms(G) ≥ −2 is proved to be (1, 0)-colorable, and we construct an infinite series of non-(1, 0)-colorable graphs G with Ms(G) = −3.

KW - Coloring

KW - Girth

KW - Planar graphs

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

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

U2 - 10.1134/S0037446611050041

DO - 10.1134/S0037446611050041

M3 - Article

AN - SCOPUS:84937644690

SN - 0037-4466

VL - 52

SP - 796

EP - 801

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

IS - 5

ER -