RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2011 Volume 52, Number 5, Pages 1004–1010 (Mi smj2253)

This article is cited in 22 papers

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

O. V. Borodinab, A. V. Kostochkaac

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c University of Illinois, Urbana, USA

Abstract: A graph $G$ is $(1,0)$-colorable if its vertex set can be partitioned into subsets $V_1$ and $V_0$ so that in $G[V_1]$ every vertex has degree at most $1$, while $G[V_0]$ is edgeless. We prove that every graph with maximum average degree at most $\frac{12}5$ is $(1,0)$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 $\frac{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)\ge-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$.

Keywords: planar graphs, coloring, girth.

UDC: 519.17

Received: 15.07.2010


 English version:
Siberian Mathematical Journal, 2011, 52:5, 796–801

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024