Vertex elimination orderings for hereditary graph classes
From MaRDI portal
Publication:2514166
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.
Recommendations
Cites work
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Square-3PC(\cdot, \cdot)-Free Berge Graphs
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- Bisimplicial vertices in even-hole-free graphs
- Claw-free graphs. IV: Decomposition theorem
- Decomposition of even-hole-free graphs with star cutsets and 2-joins
- Even and odd holes in cap-free graphs
- Even-hole-free graphs. I: Decomposition theorem
- Even-hole-free graphs: A survey
- Graphs that do not contain a cycle with a node that has at least two neighbors on it
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 6783420 (Why is no real title available?)
- scientific article; zbMATH DE number 4183452 (Why is no real title available?)
- scientific article; zbMATH DE number 3050594 (Why is no real title available?)
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- LexBFS-orderings and powers of chordal graphs
- On rigid circuit graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Separability generalizes Dirac's theorem
- The \(k\)-in-a-path problem for claw-free graphs
- The NP-Completeness of Some Edge-Partition Problems
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The strong perfect graph theorem
- The world of hereditary graph classes viewed through Truemper configurations
- Triangulated neighborhoods in even-hole-free graphs
- Universally signable graphs
Cited in
(20)- Structure and algorithms for (cap, even hole)-free graphs
- Decomposition techniques applied to the clique-stable set separation problem
- Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- Avoidable paths in graphs
- On the triangle clique cover and \(K_t\) clique cover problems
- Wheel-free planar graphs
- New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
- Oracles for vertex elimination orderings
- Moplex elimination orderings
- How vertex elimination can overachieve
- Vertex orderings of graphs: an overview
- On the structure of (pan, even hole)-free graphs
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
- A generalization of simplicial elimination orderings
- Shifting paths to avoidable ones
- Computing and listing avoidable vertices and paths
- Computing and listing avoidable vertices and paths
- Bisimplicial separators
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)
