Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs (Q1962062): Difference between revisions

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.