|
Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 5, Pages 1004–1010
(Mi smj2253)
|
|
|
|
This article is cited in 22 scientific papers (total 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.
Received: 15.07.2010
Citation:
O. V. Borodin, A. V. Kostochka, “Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most $1$”, Sibirsk. Mat. Zh., 52:5 (2011), 1004–1010; Siberian Math. J., 52:5 (2011), 796–801
Linking options:
https://www.mathnet.ru/eng/smj2253 https://www.mathnet.ru/eng/smj/v52/i5/p1004
|
|