Vertex elimination orderings for hereditary graph classes

DOI10.1016/J.DISC.2014.12.014zbMATH Open1306.05202DBLPjournals/dm/AboulkerCTV15arXiv1205.2535OpenAlexW2107127602WikidataQ59897244 ScholiaQ59897244MaRDI QIDQ2514166FDOQ2514166

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

Publication date: 30 January 2015

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

Abstract: We provide a general method to prove the existence and compute efficiently elimination orderings in graphs. Our method relies on several tools that were known before, but that were not put together so far: the algorithm LexBFS due to Rose, Tarjan and Lueker, one of its properties discovered by Berry and Bordat, and a local decomposition property of graphs discovered by Maffray, Trotignon and Vuvskovi'c. We use this method to prove the existence of elimination orderings in several classes of graphs, and to compute them in linear time. Some of the classes have already been studied, namely even-hole-free graphs, square-theta-free Berge graphs, universally signable graphs and wheel-free graphs. Some other classes are new. It turns out that all the classes that we study in this paper can be defined by excluding some of the so-called Truemper configurations. For several classes of graphs, we obtain directly bounds on the chromatic number, or fast algorithms for the maximum clique problem or the coloring problem.

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

Recommendations

• How vertex elimination can overachieve
• Vertex orderings of graphs: an overview
• Moplex elimination orderings
• On the semi-perfect elimination
• A generalization of simplicial elimination orderings

zbMATH Keywords

elimination orderinglexbfsTruemper configurationsalgorithms for classes of graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On rigid circuit graphs
• The strong perfect graph theorem
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Algorithmic Aspects of Vertex Elimination on Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Claw-free graphs. IV: Decomposition theorem
• The NP-Completeness of Some Edge-Partition Problems
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Separability generalizes Dirac's theorem
• Even-hole-free graphs: A survey
• Universally signable graphs
• Even-hole-free graphs. I: Decomposition theorem
• Even and odd holes in cap-free graphs
• LexBFS-orderings and powers of chordal graphs
• Title not available (Why is that?)
• Bisimplicial vertices in even-hole-free graphs
• Decomposition of even-hole-free graphs with star cutsets and 2-joins
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• Triangulated neighborhoods in even-hole-free graphs
• The \(k\)-in-a-path problem for claw-free graphs
• The world of hereditary graph classes viewed through Truemper configurations

Cited In (19)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2514166)