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 - Funding Information:
The first author was supported by the Russian Foundation for Basic Research (Grants 08–01–00673 and 09– 01–00244). The second author was supported by the NSF grant DMS–0965587 and the Ministry for Education and Science of the Russian Federation (Grant 14.740.11.0868).
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 -