Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
For a graph \(G = (V,E)\) a linear ordering \(\sigma\) of the vertices is called a strong ordering of \(G\) if the following property is fulfilled: if \(ab, ac, bd \in E\), \(a <_{\sigma} d\) and \(b <_{\sigma} c\) then \(cd \in E\). In this paper the author considers strongly orderable graphs, i.e.\ graphs that admit a strong ordering of its vertices. Two new characterizations for this class of graphs are presented using elimination orderings on the vertices (quasi-simple elimination) and the edges (simplicial-edge-without-vertex elimination), respectively. These elimination orderings generalize characterizing elimination orderings for strongly chordal and chordal bipartite graphs. It is shown that a strong ordering of a strongly orderable graph can be found in \(O(|V|+ |E|)|V|\) time, leading to a \(O(|V|+ |E|)|V|\) time algorithm for recognizing strongly orderable graphs. Furthermore, the author proves that the class of strongly chordal graphs is properly contained in the class of weakly triangulated graphs that do not contain a sun as induced subgraph. Finally, greedy algorithms for computing minimum coloring, maximum clique, minimum clique partition, and maximum independent set on strongly orderable graphs are given, that run in linear time, provided a special strong ordering (lexicographic quasi-simple elimination ordering) is given.
- A characterization of perfect graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Characterizations of strongly chordal graphs
- Characterizations of totally balanced matrices
- Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
- Domination, independent domination, and duality in strongly chordal graphs
- Doubly lexical ordering of dense 0--1 matrices
- Doubly Lexical Orderings of Matrices
- Greedoids
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3891425 (Why is no real title available?)
- scientific article; zbMATH DE number 1107732 (Why is no real title available?)
- Labeling algorithms for domination problems in sun-free chordal graphs
- Matching and multidimensional matching in chordal and strongly chordal graphs
- Perfect Elimination and Chordal Bipartite Graphs
- Steiner trees, connected domination and strongly chordal graphs
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Three Partition Refinement Algorithms
- Weakly triangulated graphs
- Computing a minimum paired-dominating set in strongly orderable graphs
- Finding a sun in building-free graphs
- Perfect circular arc coloring
- Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
- scientific article; zbMATH DE number 1302027 (Why is no real title available?)
- \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
- scientific article; zbMATH DE number 2086689 (Why is no real title available?)
- Edge erasures and chordal graphs
- The Perfect Matching Reconfiguration Problem
- The graphs that Dahlhaus called ``good generalized strongly chordal
- Strong Chordality of Graphs with Possible Loops
- Coloring squares of graphs via vertex orderings
- Strong Cocomparability Graphs and Slash-Free Orderings of Matrices
- Gallai-like characterization of strong cocomparability graphs
- Reconfiguring planar perfect matchings via bounded length alternating cycles
- Koszul binomial edge ideals
This page was built for publication: Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962062)
