Hadwiger Number of Graphs with Small Chordality
Publication:2945190
DOI10.1007/978-3-319-12340-0_17zbMath1417.05209arXiv1406.3812OpenAlexW1853176571MaRDI QIDQ2945190
Pim van 't Hof, Petr A. Golovach, Christophe Paul, Pinar Heggernes
Publication date: 9 September 2015
Published in: SIAM Journal on Discrete Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.3812
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Approximating the maximum clique minor and some subgraph homeomorphism problems
- Bipartite permutation graphs
- Hadwiger's conjecture is true for almost every graph
- A simple linear time algorithm for cograph recognition
- Algorithmic graph theory and perfect graphs
- Graph minors. XIII: The disjoint paths problem
- Connected matchings in chordal bipartite graphs
- Contracting graphs to paths and trees
- Contracting Few Edges to Remove Forbidden Induced Subgraphs
- On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Finding Large Clique Minors is Hard
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Linear Recognition Algorithm for Cographs
- Graph Classes: A Survey
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Asteroidal Triple-Free Graphs
- The complexity of satisfiability problems