Equitable vertex arboricity conjecture holds for graphs with low degeneracy

DOI10.1007/S10114-021-0663-4MaRDI QIDQ2230570zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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 -coloring of graphs with low average degree

Cites work

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