Abstract
It is proved that the vertex set of any simple graph G can be equitably partitioned into k subsets for any integer \(k\ge \max \{\big \lceil \frac{\Delta (G)+1}{2}\big \rceil ,\big \lceil \frac{|G|}{4}\big \rceil \}\) so that each of them induces a linear forest.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy JA, Murty USR (2008) Graph theory. GTM, vol 244. Springer, Berlin
Chen G, Gao Y, Shan S, Wang G, Wu J-L (2017) Equitable vertex arboricity of \(5\)-degenerate graphs. J Comb Optim 34(2):426–432
Esperet L, Lemoine L, Maffray F (2015) Equitable partition of graphs into induced forests. Discrete Math 338:1481–1483
Niu B, Zhang X, Gao Y (2019) Equitable partition of plane graphs with independent crossings into induced forests. arXiv:1903.08337 [math.CO]
Wu J-L, Zhang X, Li H (2013) Equitable vertex arboricity of graphs. Discrete Math 313(23):2696–2701
Zhang X (2015) Equitable vertex arboricity of planar graphs. Taiwan J Math 19(1):123–131
Zhang X (2016) Equitable vertex arboricity of subcubic graphs. Discrete Math 339:1724–1726
Zhang X, Wu J-L (2014) A conjecture on equitable vertex arboricity of graphs. Filomat 28(1):217–219
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Xin Zhang: Supported by the National Natural Science Foundation of China (No. 11871055) and the Youth Talent Support Plan of Xi’an Association for Science and Technology (No. 2018-6).
Rights and permissions
About this article
Cite this article
Zhang, X., Niu, B. Equitable partition of graphs into induced linear forests. J Comb Optim 39, 581–588 (2020). https://doi.org/10.1007/s10878-019-00498-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00498-8