A conjecture on equitable vertex arboricity of graphs

DOI10.2298/FIL1401217ZzbMATH Open1464.05159arXiv1211.4998WikidataQ122943777 ScholiaQ122943777MaRDI QIDQ2975465FDOQ2975465

Authors: Xin Zhang, Jian-Liang Wu 

Publication date: 11 April 2017

Published in: Filomat (Search for Journal in Brave)

Abstract: Wu, Zhang and Li [4] conjectured that the set of vertices of any simple graph $G$ can be equitably partitioned into $lceil(Delta(G)+1)/2ceil$ subsets so that each of them induces a forest of $G$. In this note, we prove this conjecture for graphs $G$ with $Delta(G)geq|G|/2$.

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

Recommendations

• Equitable vertex arboricity of 5-degenerate graphs
• Equitable vertex arboricity of planar graphs
• Equitable partition of graphs into induced linear forests
• Equitable vertex arboricity of subcubic graphs
• Equitable partition of graphs into induced forests

zbMATH Keywords

maximum degreetree coloringrelaxed coloringequitable vertex arboricity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15)

Cited In (11)

• Equitable vertex arboricity of subcubic graphs
• Theoretical aspects of equitable partition of networks into sparse modules
• On equitable list arboricity of graphs
• Complexity of tree-coloring interval graphs equitably
• Hardness and algorithms of equitable tree-coloring problem in chordal graphs
• Equitable vertex arboricity conjecture holds for graphs with low degeneracy
• Equitable partition of graphs into induced linear forests
• Equitable partition of plane graphs with independent crossings into induced forests
• Equitable vertex arboricity of 5-degenerate graphs
• Equitable list point arboricity of graphs
• Equitable vertex arboricity of planar graphs

This page was built for publication: A conjecture on equitable vertex arboricity of graphs

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