Complexity of tree-coloring interval graphs equitably

DOI10.1007/978-3-030-57602-8_35zbMath1482.68183arXiv2003.03945OpenAlexW3080346353MaRDI QIDQ2039688

Xin Zhang, Bi Li, Bei Niu

Publication date: 5 July 2021

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

zbMATH Keywords

interval graphcommunication networklinear-time algorithmW[1-hardness]equitable tree-coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

Hardness and algorithms of equitable tree-coloring problem in chordal graphs ⋮ Theoretical aspects of equitable partition of networks into sparse modules

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Equitable vertex arboricity of subcubic graphs
• Equitable vertex arboricity of graphs
• An optimal greedy heuristic to color interval graphs
• Bin packing with fixed number of bins revisited
• Tree-coloring problems of bounded treewidth graphs
• 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
• Graph Theory
• A conjecture on equitable vertex arboricity of graphs
• Bin Packing with Fixed Number of Bins Revisited
• Equitable list vertex colourability and arboricity of grids

This page was built for publication: Complexity of tree-coloring interval graphs equitably