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.     

A proof of Hougardy's conjecture for diamond-free graphs

A pair of vertices of a graph is called an even pair if every chordless path between them has an even number of edges. A graph is minimally even pair free if it is not a clique, contains no even pair, but every proper induced subgraph either contains an even pair or is a clique. Hougardy (European J. Combin. 16 (1995) 17–21) conjectured that a minimally even pair free graph is either an odd cycle of length at least five, the complement of an even or odd cycle of length at least five, or the linegraph of a bipartite graph. A diamond is a graph obtained from a complete graph on four vertices by removing an edge. In this paper we verify Hougardy's conjecture for diamond-free graphs by adapting the characterization of perfect diamond-free graphs given by Fonlupt and Zemirline (Maghreb Math. Rev. 1 (1992) 167–202).     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

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.     

Berge graphs with chordless cycles of bounded length

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C₃ or to C₄. The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200–208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C₄ by an arbitrary C_p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p ≥ 6, the graphs whose cycles are isomorphic either to C₃ or to one of C_p, C_p+2, …, C_{2p 6} are perfect. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 73–79, 1999     

Discs in unbreakable graphs

We show that every vertex in an unbreakable graph is in a disc, where a disc is a chordless cycle, or the complement of a chordless cycle, with at least five vertices. A corollary is that every vertex in a minimal imperfect graph is in a disc.This research was supported by NSERC Operating Grant OGP-0137764.     

On brittle graphs

Chvátal defined a graph G to be brittle if each induced subgraph F of G contains a vertex that is not a midpoint of any P₄ or not an endpoint of any P₄. Every brittle graph is perfectly orderable. In this paper, we prove that a graph is brittle whenever it is HHD-free (containing no chordless cycle with at least five vertices, no cycle on six vertices with a long chord, and no complement of the chordless path on five vertices). We also design an O(n₄) algorithm to recognize HHD-free graphs, and also an O(n₄) algorithm to construct a perfect order of an HHD-free graph. It follows from this result that an optimal coloring and a largest clique of an HHD-free graph can be found in O(n₄) time.     

Most unbreakable murky graphs are bull-free

A bull is the (self-complementary) graph with nodesa, b, c, d, e and edgesab, ac, bc, bd,ce. A star cutset in a graph G is a set C of nodes such thatG-C is disconnected, and such that some node inC is adjacent to all remaining nodes inC. A graph is called unbreakable if it has more than two nodes and if neither the graph nor its complement has a star cutset. Hayward defined a graphG to be murky if neitherG nor its complement contains a chordless cycle with five nodes or a chordless path with six nodes. We prove that most unbreakable murky graphs are bull-free. This leads, via a result of Chvátal and Sbihi, to a shortening of Hayward’s proof that murky graphs are perfect.     

On the P4-structure of perfect graphs. II. Odd decompositions

We prove that a graph is perfect if its vertices can be coloured by two colours in such a way that each induced chordless path with four vertices has an odd number of vertices of each colour. Using this result, we prove a decomposition theorem for perfect graphs; this theorem is defined in terms of the chordless path with four vertices.     

On the strong perfect graph conjecture

A graph G is perfect if for every induced subgraph H of G the chromatic number χ(H) equals the largest number ω(H) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G¯ contains an odd chordless cycle of length at least 5. Its resolution has eluded researchers for more than 20 years. We prove that the conjecture is true for a class of graphs that we describe by forbidden configurations.     

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     

Asteroids in rooted and directed path graphs

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.     

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.     

On a Class of P5-Free Graphs

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement ? contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P₅-free graphs.     

Opposition graphs are strict quasi-parity graphs

An opposition graph is a graph whose edges can be acyclically oriented in such a way that every chordless path on four vertices has its extreme edges both pointing in or pointing out. A strict quasi-parity graph is a graphG such that every induced subgraphH ofG either is a clique or else contains a pair of vertices which are not endpoints of an odd (number of edges) chordless path ofH. The perfection of opposition graphs and strict quasi-parity graphs was established respectively by Olariu and Meyniel. We show here that opposition graphs are strict quasi-parity graphs.The second author acknowledges the support of the Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

Some properties of minimal imperfect graphs

The Even Pair Lemma, proved by Meyniel, states that no minimal imperfect graph contains a pair of vertices such that all chordless paths joining them have even lengths. This Lemma has proved to be very useful in the theory of perfect graphs. The Odd Pair Conjecture, with ‘even’ replaced by ‘odd’, is the natural analogue of the Even Pair Lemma. We prove a partial result for this conjecture, namely: no minimal imperfect graph G contains a three-pair, i.e. two nonadjacent vertices u₁, u₂ such that all chordless paths of G joining u₁ to u₂ contain precisely three edges. As a by-product, we obtain short proofs of two previously known theorems: the first one is a well-known theorem of Meyniel (a graph is perfect if each of its odd cycles with at least five vertices contains at least two chords), the second one is a theorem of Olariu (a graph is perfect if it contains no odd antihole, no P₅ and no extended claw as induced subgraphs).     

Characterizing directed path graphs by forbidden asteroids

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non‐adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex‐disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:103‐112, 2011     

Families of graphs complete for the strong perfect graph Conjecture

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.     

Wings and perfect graphs

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G — C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. V. Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.     

Bull-free Berge graphs are perfect

Abull is the (self-complementary) graph with verticesa, b, c, d, e and edgesab, ac, bc, bd, ce; a graphG is calledBerge if neitherG not its complement contains a chordless cycle whose length is odd and at least five. We prove that bull-free Berge graphs are perfect; a part of our argument relies on a new property of minimal imperfect graphs.This work was done while both authors were at the School of Computer Science, McGill University; support by NSERC is gratefully acknowledged.