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
- 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?)
- 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
- 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 NP-Completeness of Some Edge-Partition Problems
- The Ramsey number R(3, t) has order of magnitude t2/log t
- The \(k\)-in-a-path problem for claw-free graphs
- 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
(19)- Bisimplicial separators
- 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
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
- 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
- Avoidable paths in graphs
- Computing and listing avoidable vertices and paths
- 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)
