Equitable partition of graphs into induced linear forests

DOI10.1007/S10878-019-00498-8MaRDI QIDQ2292162zbMATH OpenOpenAlexFDO

Authors Xin Zhang, Bei Niu

Publication date 3 February 2020

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.05075

zbMATH Keywords

equitable coloringvertex arboricitylinear forest

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: It is proved that the vertex set of any simple graph $G$ can be equitably partitioned into $k$ subsets for any integer $$ so that each of them induces a linear forest.

Recommendations

• Equitable partition of graphs into induced forests
• Equitable vertex arboricity of subcubic graphs
• Equitable partition of planar graphs
• A conjecture on equitable vertex arboricity of graphs
• Equitable vertex arboricity of planar graphs

Cites work

• A conjecture on equitable vertex arboricity of graphs
• Equitable partition of graphs into induced forests
• Equitable partition of plane graphs with independent crossings into induced forests
• Equitable vertex arboricity of 5-degenerate graphs
• Equitable vertex arboricity of graphs
• Equitable vertex arboricity of planar graphs
• Equitable vertex arboricity of subcubic graphs
• Graph theory

Cited in

(14)

• Hardness and algorithms of equitable tree-coloring problem in chordal graphs
• Equitable partitions to spanning trees in a graph
• Equitable vertex arboricity conjecture holds for graphs with low degeneracy
• Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs
• A Rooted-Forest Partition with Uniform Vertex Demand
• Complexity of tree-coloring interval graphs equitably
• Equitable partition of graphs into induced forests
• Theoretical aspects of equitable partition of networks into sparse modules
• Equitable vertex arboricity of 5-degenerate graphs
• Equitable partition of plane graphs with independent crossings into induced forests
• On equitable list arboricity of graphs
• A conjecture on equitable vertex arboricity of graphs
• Equitable vertex arboricity of subcubic graphs
• Equitable partition of planar graphs

This page was built for publication: Equitable partition of graphs into induced linear forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292162)