×

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.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Appel K. and Haken W., ”Every planar map is four colorable. Part I. Discharging,” Illinois J. Math., 21, 429–490 (1977). · Zbl 0387.05009
[2] Appel K. and Haken W., ”Every planar map is four colorable. Part II. Reducibility,” Illinois J. Math., 21, 491–567 (1977). · Zbl 0387.05010
[3] 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
[4] 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
[5] 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
[6] 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
[7] 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.