×

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
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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
[2] Appel, K.; Haken, W., Every planar map is four colorable. I. Discharging, Illinois J. Math., 21, 3, 429-490 (1977) · Zbl 0387.05009
[3] 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
[4] 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
[5] 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
[6] Borodin, O. V.; Kostochka, A. V., Defective 2-colorings of sparse graphs, J. Combin. Theory Ser. B, 104, 72-80 (2014) · Zbl 1282.05041
[7] 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
[8] 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
[9] 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
[10] 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
[11] Dvořák, Z.; Norin, S., Islands in minor-closed classes. I. Bounded treewidth and separators (2017), arXiv preprint arXiv:1710.02727
[12] 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
[13] Esperet, L.; Ochem, P., Islands in graphs on surfaces, SIAM J. Discrete Math., 30, 1, 206-219 (2016) · Zbl 1329.05105
[14] Goddard, W., Acyclic colorings of planar graphs, Discrete Math., 91, 1, 91-94 (1991) · Zbl 0742.05041
[15] 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
[16] 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
[17] Poh, K. S., On the linear vertex-arboricity of a planar graph, J. Graph Theory, 14, 1, 73-75 (1990) · Zbl 0705.05016
[18] Š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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.