Hadwiger Number of Graphs with Small Chordality

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

zbMATH Keywords

cographsAT-free graphsHadwiger numberbipartite permutation graphs

Mathematics Subject Classification ID

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

Hadwiger's conjecture for squares of 2-trees, Contraction Blockers for Graphs with Forbidden Induced Paths, Parameterized complexity of multicut in weighted trees, Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions, Unnamed Item, Contraction and deletion blockers for perfect graphs and \(H\)-free graphs, Reducing graph transversals via edge contractions, Multitasking Capacity: Hardness Results and Improved Constructions

Uses Software

• Algorithm 97

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