3-colouring for dually chordal graphs and generalisations

DOI10.1016/j.ipl.2017.07.012zbMath1420.05060OpenAlexW2744198939MaRDI QIDQ2404614

Arne Leitert

Publication date: 19 September 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.07.012

zbMATH Keywords

polynomial-time algorithmgraph algorithms3-colourabilitydually chordal graphstree-breadth

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Burning Two Worlds ⋮ On the complexity of computing treebreadth ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Cites Work

• Unnamed Item
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• The strong perfect graph theorem
• On bridged graphs and cop-win graphs
• Dismantling absolute retracts of reflexive graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• On the Complexity of Computing Treebreadth
• Dually Chordal Graphs
• Reducibility among Combinatorial Problems

This page was built for publication: 3-colouring for dually chordal graphs and generalisations