# zbMATH — the first resource for mathematics

Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1. (English) Zbl 1232.05073
Sib. Math. J. 52, No. 5, 796-801 (2011); translation from Sib. Mat. Zh. 52, No. 5, 1004-1011 (2011).
Summary: 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)$$-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) \geq - 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$$.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
planar graphs; coloring; girth
Full Text:
##### References:
  Appel K. and Haken W., ”Every planar map is four colorable. Part I. Discharging,” Illinois J. Math., 21, 429–490 (1977). · Zbl 0387.05009  Appel K. and Haken W., ”Every planar map is four colorable. Part II. Reducibility,” Illinois J. Math., 21, 491–567 (1977). · Zbl 0387.05010  Cowen L. J., Cowen R. H., and Woodall D. R., ”Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency,” J. Graph Theory, 10, 187–195 (1986). · Zbl 0596.05024 · doi:10.1002/jgt.3190100207  Havet F. and Sereni J.-S., ”Improper choosability of graphs and maximum average degree,” J. Graph Theory, 52, 181–199 (2006). · Zbl 1104.05026 · doi:10.1002/jgt.20155  Glebov A. N. and Zambalaeva D. Zh., ”Path partitions of planar graphs,” Sib. Elektron. Mat. Izv., 4, 450–459 (2007) ( http://semr.math.nsc.ru ). · Zbl 1132.05315  Borodin O. V. and Ivanova A. O., ”Almost proper vertex 2-colorings of sparse graphs,” Diskretn. Anal. Issled. Oper., 16, No. 2, 16–20 (2009). · Zbl 1249.05110  Borodin O. V., Ivanova A. O., Montassier M., Ochem P., and Raspaud A., ”Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k,” J. Graph Theory, 65, 83–93 (2010). · Zbl 1209.05177 · doi:10.1002/jgt.20467
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.