# zbMATH — the first resource for mathematics

Partitioning sparse graphs into an independent set and a graph with bounded size components. (English) Zbl 1441.05179
Summary: We study the problem of partitioning the vertex set of a given graph so that each part induces a graph with components of bounded order; we are also interested in restricting these components to be paths. In particular, we say a graph $$G$$ admits an $$( \mathcal{I} , \mathcal{O}_k )$$-partition if its vertex set can be partitioned into an independent set and a set that induces a graph with components of order at most $$k$$. We prove that every graph $$G$$ with $$\mathrm{mad}( G ) < \frac{ 5}{ 2}$$ admits an $$( \mathcal{I} , \mathcal{O}_3 )$$-partition. This implies that every planar graph with girth at least 10 can be partitioned into an independent set and a set that induces a graph whose components are paths of order at most 3. We also prove that every graph $$G$$ with $$\mathrm{mad}( G ) < \frac{ 8 k}{ 3 k + 1} = \frac{ 8}{ 3} \left( 1 - \frac{ 1}{ 3 k + 1}\right)$$ admits an $$( \mathcal{I} , \mathcal{O}_k )$$-partition. This implies that every planar graph with girth at least 9 can be partitioned into an independent set and a set that induces a graph whose components have order at most 9.
##### MSC:
 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C42 Density (toughness, etc.) 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text:
##### References:
  Alon, N.; Ding, G.; Oporowski, B.; Vertigan, D., Partitioning into graphs with only small components, J. Combin. Theory Ser. B, 87, 2, 231-243 (2003) · Zbl 1023.05045  Appel, K.; Haken, W., Every planar map is four colorable. I. Discharging, Illinois J. Math., 21, 3, 429-490 (1977) · Zbl 0387.05009  Appel, K.; Haken, W.; Koch, J., Every planar map is four colorable. II. Reducibility, Illinois J. Math., 21, 3, 491-567 (1977) · Zbl 0387.05010  Axenovich, M.; Ueckerdt, T.; Weiner, P., Splitting planar graphs of girth 6 into two linear forests with short paths, J. Graph Theory, 85, 3, 601-618 (2017) · Zbl 1367.05044  Borodin, O. V.; Ivanova, A. O., List strong linear 2-arboricity of sparse graphs, J. Graph Theory, 67, 2, 83-90 (2011) · Zbl 1218.05038  Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041  Borodin, O. V.; Kostochka, A. V.; Yancey, M., On 1-improper 2-coloring of sparse graphs, Discrete Math., 313, 22, 2638-2649 (2013) · Zbl 1281.05060  Choi, H.; Choi, I.; Jeong, J.; Suh, G., $$(1, k)$$-coloring of graphs with girth at least five on a surface, J. Graph Theory, 84, 4, 521-535 (2017) · Zbl 1359.05099  Choi, I.; Raspaud, A., Planar graphs with girth at least $$5$$ are $$( 3 , 5 )$$-colorable, Discrete Math., 338, 4, 661-667 (2015) · Zbl 1305.05072  Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M., The complexity of multiterminal cuts, SIAM J. Comput., 23, 4, 864-894 (1994) · Zbl 0809.68075  Dvořák, Z.; Norin, S., Islands in minor-closed classes. I. Bounded treewidth and separators (2017), arXiv preprint arXiv:1710.02727  Esperet, L.; Montassier, M.; Ochem, P.; Pinlou, A., A complexity dichotomy for the coloring of sparse graphs, J. Graph Theory, 73, 1, 85-102 (2013) · Zbl 1264.05049  Esperet, L.; Ochem, P., Islands in graphs on surfaces, SIAM J. Discrete Math., 30, 1, 206-219 (2016) · Zbl 1329.05105  Goddard, W., Acyclic colorings of planar graphs, Discrete Math., 91, 1, 91-94 (1991) · Zbl 0742.05041  Grötzsch, H., Zur theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Nat. Reihe, 8, 109-120 (1958), /1959  Montassier, M.; Ochem, P., Near-colorings: non-colorable graphs and NP-completeness, Electron. J. Combin., 22, 1, 13 (2015), Paper 1.57 · Zbl 1308.05052  Poh, K. S., On the linear vertex-arboricity of a planar graph, J. Graph Theory, 14, 1, 73-75 (1990) · Zbl 0705.05016  Škrekovski, R., List improper colorings of planar graphs with prescribed girth, Discrete Math., 214, 1-3, 221-233 (2000) · Zbl 0940.05027
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.