Four classes of perfectly orderable graphs

A graph is called “perfectly orderable” if its vertices can be ordered in such a way that, for each induced subgraph F, a certain “greedy” coloring heuristic delivers an optimal coloring of F. No polynomial-time algorithm to recognize these graphs is known. We present four classes of perfectly orderable graphs: Welsh–Powell perfect graphs, Matula perfect graphs, graphs of Dilworth number at most three, and unions of two threshold graphs. Graphs in each of the first three classes are recognizable in a polynomial time. In every graph that belongs to one of the first two classes, we can find a largest clique and an optimal coloring in a linear time.     

On the complexity of recognizing perfectly orderable graphs

The question whether a polynomial time recognition algorithm for the class of perfectly orderable graphs exists was posed by Chvátal in 1981 when he introduced the notion of perfect orders. Since then several classes of perfectly orderable graphs have been identified. In this note we prove that recognizing perfectly orderable graphs is NP-complete.     

Alternating orientation and alternating colouration of perfect graphs

We establish a property of minimal imperfect graphs, and use this property to generate two classes of perfect graphs. The first class contains all comparability graphs, all triangulated graphs, and two other classes of perfect graphs. The second class contains all triangulated graphs and all line-graphs of bipartite graphs.     

On a conjecture of Hoàng and Tu concerning perfectly orderable graphs

Hoàng and Tu [On the perfect orderability of unions of two graphs, J. Graph Theory 33 (2000) 32-43] conjectured that a weakly triangulated graph which does not contain a chordless path with six vertices is perfectly orderable. We present a counter example to this conjecture.     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

Disjoint clique cutsets in graphs without long holes

A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005     

On superperfect noncomparability graphs

The class of superperfect graphs, which was previously studied by A. J. Hoffman, E. L. Johnson, and M. C. Golumbic, is a proper subclass of the class of perfect graphs; further, it properly contains the class of comparability graphs. In his book, Golumbic proves that, for split graphs, G is a comparability graph if and only if G is superperfect. Moreover, the fact that split graphs are exactly those graphs which are both triangulated and cotriangulated motivated Golumbic to ask if it is true or false that, for triangulated (or cotriangulated) graphs, G is a comparability graph if and only if G is superperfect. In the present paper, we determine those members of Gallai's list of minimal noncomparability graphs which are superperfect and, as a consequence, we find that the answer to the above question is “false” for triangulated and “true” for cotriangulated graphs.     

Which line-graphs are perfectly orderable?

We characterize (by forbidden induced subgraphs) those line-graphs that are perfectly orderable. Implicit in our presentation is a polynomial, time algorithm for recognizing these graphs.     

Ramsey-Type Results for Unions of Comparability Graphs

 It is well known that the comparability graph of any partially ordered set of n elements contains either a clique or an independent set of size at least . In this note we show that any graph of n vertices which is the union of two comparability graphs on the same vertex set, contains either a clique or an independent set of size at least . On the other hand, there exist such graphs for which the size of any clique or independent set is at most n ^0.4118. Similar results are obtained for graphs which are unions of a fixed number k comparability graphs. We also show that the same bounds hold for unions of perfect graphs. Received: November 1, 1999 Final version received: December 1, 2000     

Bounding the Clique‐Width of H‐Free Chordal Graphs

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P₄‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K₄‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.     

A generalization of simplicial elimination orderings

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P₄ and no 2K₂. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc.     

Optimizing weakly triangulated graphs

A graph is weakly triangulated if neither the graph nor its complement contains a chordless cycle with five or more vertices as an induced subgraph. We use a new characterization of weakly triangulated graphs to solve certain optimization problems for these graphs. Specifically, an algorithm which runs inO((n + e)n ³) time is presented which solves the maximum clique and minimum colouring problems for weakly triangulated graphs; performing the algorithm on the complement gives a solution to the maximum stable set and minimum clique covering problems. Also, anO((n + e)n ⁴) time algorithm is presented which solves the weighted versions of these problems.The author acknowledges the support of an N.S.E.R.C. Canada postgraduate scholarship.The author acknowledges the support of the U.S. Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

Tolerance graphs

Tolerance graphs arise from the intersection of intervals with varying tolerances in a way that generalizes both interval graphs and permutation graphs. In this paper we prove that every tolerance graph is perfect by demonstrating that its complement is perfectly orderable. We show that a tolerance graph cannot contain a chordless cycle of length greater than or equal to 5 nor the complement of one. We also discuss the subclasses of bounded tolerance graphs, proper tolerance graphs, and unit tolerance graphs and present several possible applications and open questions.     

Computing clique and chromatic number of circular-perfect graphs in polynomial time

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel et al. in Combinatorica 1(2):169–197, 1981). Perfect graphs have the key property that clique and chromatic number coincide for all induced subgraphs; we address the question whether the algorithmic results for perfect graphs can be extended to graph classes where the chromatic number of all members is bounded by the clique number plus one. We consider a well-studied superclass of perfect graphs satisfying this property, the circular-perfect graphs, and show that for such graphs both clique and chromatic number are computable in polynomial time as well. In addition, we discuss the polynomial time computability of further graph parameters for certain subclasses of circular-perfect graphs. All the results strongly rely upon Lovász’s Theta function.     

Clique-cutsets beyond chordal graphs

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (eg, the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. Furthermore, we obtain polynomial -bounding functions for these classes.     

Bull-Free Weakly Chordal Perfectly Orderable Graphs

 Using doubly lexical orders and the notion of box partition due to de Figueiredo, Maffray, and Porto, we show that a certain subclass of bull-free weakly chordal graphs is perfectly orderable. This together with results of de Figueiredo, Maffray, and Porto confirms Chvátal's conjecture that bull-free graphs with no anti-hole and no odd hole are perfectly orderable; here hole means induced cycle with five or more vertices. Received: September 21, 1998?Final version received: January 23, 2001     

Weakly triangulated graphs

A graph is triangulated if it has no chordless cycle with four or more vertices. It follows that the complement of a triangulated graph cannot contain a chordless cycle with five or more vertices. We introduce a class of graphs (namely, weakly triangulated graphs) which includes both triangulated graphs and complements of triangulated graphs (we define a graph as weakly triangulated if neither it nor its complement contains a chordless cycle with five or more vertices). Our main result is a structural theorem which leads to a proof that weakly triangulated graphs are perfect.     

On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case

 A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case. Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward to establish Chvátal's conjecture for this restricted case and therefore in full. Received: November 26, 1997?Final version received: February 27, 2001     

Grid Intersection Graphs and Order Dimension

We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation on these classes. Order dimension plays a role in many arguments.     

Linear Clique‐Width for Hereditary Classes of Cographs

The class of cographs is known to have unbounded linear clique‐width. We prove that a hereditary class of cographs has bounded linear clique‐width if and only if it does not contain all quasi‐threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.