Tree-coloring problems of bounded treewidth graphs

DOI10.1007/S10878-019-00461-7MaRDI QIDQ2292136zbMATH OpenOpenAlexWikidataFDO

Authors Bi Li, Xin Zhang

Publication date 3 February 2020

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

Full work available at URL https://doi.org/10.1007/s10878-019-00461-7

zbMATH Keywords

bounded treewidthtree-coloringequitable tree-coloringNice tree decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• Mathematical Foundations of Computer Science 2004
• Equitable colorings of bounded treewidth graphs
• On the complexity of some colorful problems parameterized by treewidth
• scientific article; zbMATH DE number 7058467

Cites work

• A \(c^k n\) 5-approximation algorithm for treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Acyclic colorings of planar graphs
• Confronting intractability via parameters
• Critical Point-Arboritic Graphs
• Equitable Coloring
• Equitable coloring of graph product
• Equitable colorings of bounded treewidth graphs
• Equitable colorings of planar graphs without short cycles
• Equitable partition of graphs into induced forests
• Equitable vertex arboricity of 5-degenerate graphs
• Equitable vertex arboricity of graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Interval vertex-coloring of a graph with forbidden colors
• On Equitable Coloring of d-Degenerate Graphs
• On the complexity of some colorful problems parameterized by treewidth
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• The Point-Arboricity of Planar Graphs

Cited in

(18)

• Hardness and algorithms of equitable tree-coloring problem in chordal graphs
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• Equitable vertex arboricity conjecture holds for graphs with low degeneracy
• On the complexity of some colorful problems parameterized by treewidth
• On an extremal problem for colored trees
• Minimum conflict free colouring parameterized by treewidth
• Extremal problems on detectable colorings of trees
• The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing
• Complexity of tree-coloring interval graphs equitably
• More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
• \(H\)-free coloring on graphs with bounded tree-width
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Theoretical aspects of equitable partition of networks into sparse modules
• On digraph coloring problems and treewidth duality
• Equitable colorings of bounded treewidth graphs
• Equitable partition of plane graphs with independent crossings into induced forests
• scientific article; zbMATH DE number 6423647 (Why is no real title available?)
• What makes equitable connected partition easy

This page was built for publication: Tree-coloring problems of bounded treewidth graphs

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