Equitable vertex arboricity conjecture holds for graphs with low degeneracy

DOI10.1007/S10114-021-0663-4zbMATH Open1473.05098arXiv1908.05066OpenAlexW3197826830WikidataQ113904804 ScholiaQ113904804MaRDI QIDQ2230570FDOQ2230570

Authors: Xin Zhang, Bei Niu, Yan Li, Bi Li 

Publication date: 24 September 2021

Published in: Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Abstract: The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations. Namely, an equitable tree-$k$-coloring of a graph is a vertex coloring using $k$ distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one. In this paper, we show some theoretical results on the equitable tree-coloring of graphs by proving that every $d$-degenerate graph with maximum degree at most $Delta$ is equitably tree-$k$-colorable for every integer $kgeq(Delta+1)/2$ provided that $Deltageq9.818d$, confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.

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

Recommendations

• On Equitable Coloring of d-Degenerate Graphs
• Equitable list tree-coloring of bounded treewidth graphs
• Equitable coloring of 2-degenerate graph and plane graphs without cycles of specific lengths
• Equitable vertex arboricity of 5-degenerate graphs
• On equitable \(\Delta\)-coloring of graphs with low average degree

zbMATH Keywords

degeneracyequitable coloringvertex arboricitytree-coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• Equitable partition of graphs into induced forests
• Equitable vertex arboricity of subcubic graphs
• A conjecture on equitable vertex arboricity of graphs
• Equitable vertex arboricity of graphs
• The Point-Arboricity of Planar Graphs
• Equitable Colourings of d-degenerate Graphs
• Equitable vertex arboricity of planar graphs
• Tree-coloring problems of bounded treewidth graphs
• Equitable list point arboricity of graphs
• On equitable list arboricity of graphs
• Analyzing lattice networks through substructures
• Equitable improper choosability of graphs
• Equitable list tree-coloring of bounded treewidth graphs
• Equitable partition of graphs into induced linear forests
• Equitable vertex arboricity of 5-degenerate graphs
• Equitable list vertex colourability and arboricity of grids
• The linear \((n - 1)\)-arboricity of some lexicographic product graphs

Cited In (4)

• Theoretical aspects of equitable partition of networks into sparse modules
• Equitable list tree-coloring of bounded treewidth graphs
• Equitable vertex arboricity of 5-degenerate graphs
• Fast algorithm of equitably partitioning degenerate graphs into graphs with lower degeneracy

This page was built for publication: Equitable vertex arboricity conjecture holds for graphs with low degeneracy

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