Combinatorial problems on \(H\)-graphs

DOI10.1016/j.endm.2017.06.042zbMath1378.05051arXiv1706.00575OpenAlexW2621063750MaRDI QIDQ1689915

Peter Zeman, Steven Chaplick

Publication date: 18 January 2018

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

zbMATH Keywords

treewidthisomorphismcliquecoloringintersection graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (13)

Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Unnamed Item ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ Recognizing Proper Tree-Graphs ⋮ Intersection graphs of non-crossing paths ⋮ Unnamed Item ⋮ The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation ⋮ On \(H\)-topological intersection graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

Cites Work

• Graph minors. III. Planar tree-width
• Decomposition by clique separators
• Precoloring extension. I: Interval graphs
• Generalized coloring for tree-like graphs
• Algorithmic graph theory and perfect graphs
• The maximum clique problem in multiple interval graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Graph Classes: A Survey
• Algorithm Theory - SWAT 2004
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes

This page was built for publication: Combinatorial problems on \(H\)-graphs