Vertex elimination orderings for hereditary graph classes

DOI10.1016/j.disc.2014.12.014zbMath1306.05202arXiv1205.2535OpenAlexW2107127602WikidataQ59897244 ScholiaQ59897244MaRDI QIDQ2514166

Pierre Aboulker, Nicolas Trotignon, Kristina Vušković, Pierre Charbit

Publication date: 30 January 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

elimination orderinglexbfsTruemper configurationsalgorithms for classes of graphs

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Shifting paths to avoidable ones ⋮ Computing and listing avoidable vertices and paths ⋮ Computing and listing avoidable vertices and paths ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Decomposition techniques applied to the clique-stable set separation problem ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ Avoidable paths in graphs ⋮ The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs ⋮ On the triangle clique cover and \(K_t\) clique cover problems ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Wheel-free planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• On rigid circuit graphs
• The strong perfect graph theorem
• Triangulated neighborhoods in even-hole-free graphs
• Claw-free graphs. IV: Decomposition theorem
• Bisimplicial vertices in even-hole-free graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• LexBFS-orderings and powers of chordal graphs
• Universally signable graphs
• Separability generalizes Dirac's theorem
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• The \(k\)-in-a-path problem for claw-free graphs
• Even-hole-free graphs part I: Decomposition theorem
• The world of hereditary graph classes viewed through Truemper configurations
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• The NP-Completeness of Some Edge-Partition Problems
• Algorithmic Aspects of Vertex Elimination on Graphs
• Even and odd holes in cap-free graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Even-hole-free graphs: A survey
• Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It

This page was built for publication: Vertex elimination orderings for hereditary graph classes