A Generalization of Simplicia1 Elimination Orderings*

Frederic Maff ray CNRS, LABORATOIRE LEIBNIZ, INSTITUT IMAG, BP 53

38041 GRENOBLE CEDEX 9, FRANCE e-mail: maffray@isis.imag. fr

Oscar Port0 PUC-RIO, DEPT. DE ENGENHARIA ELETRICA

RUA MARQUES DE sAo VICENTE 225, PREDIO CARDEAL LEME SALA 401, CEP 22453, RIO DE JANEIRO, RJ, BRAZIL

e-mail: oscar@ele. puc-rio. br

Myriam Preissmann CNRS, LABORATOIRE LEIBNIZ, INSTITUT IMAG, BP 53

38047 GRENOBLE CEDEX 9, FRANCE e-mail: preissma@droopy. imag. fr

ABSTRACT

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P4 and no 2K2. 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. 0 1996 John Wiley & Sons, Inc.

* The first and second authors are grateful for the support of CAPES (Brazil) and COFECUB (France). This research has been partially supported by CNPq, (Project ProComb of ProTem-11-C, Proc. 68006594/94-6).

Journal of Graph Theory Vol. 23, No. 2, 203-208 (1996) @ 1996 John Wiley & Sons, Inc. CCC 0364-9024/96/020203-06

204 JOURNAL OF GRAPH THEORY

1. INTRODUCTION

A graph is pe$ect if the vertices of any induced subgraph H can be colored, in such a way that no two adjacent vertices receive the same color, with a number of colors not exceeding the cardinality w ( H ) of a maximum clique of H . Berge introduced perfect graphs in the early 1960s (see [l , 21) and conjectured that a graph is perfect if and only if it does not contain an induced subgraph isomorphic to a chordless cycle with at least five vertices (an “odd hole”) or to the complement of such a cycle (an “odd antihole”). This problem, known as the Strong Perfect Graph Conjecture, is still open and only special cases have been solved (see e.g., [4, 111). In this paper we prove this conjecture for the graphs where every induced subgraph has a vertex whose neighborhood has no induced 2Kz or P4. The proof is an algorithm that finds an w(G)-coloring in such a graph G if it contains no odd hole or antihole. Our algorithm is sequential and with bichromatic exchanges. We also show that this class contains several well-known classes of perfect graphs such as i-triangulated graphs.

Recall that a vertex is called simplicia1 if its neighborhood induces a clique. We will say that a vertex is pretty if its neighborhood contains no 2K2 (the graph with four vertices and exactly two, nonincident, edges) and no P4 (the chordless path on four vertices). Clearly, every simplicia1 vertex is pretty. We then say that a graph is pretty if every induced subgraph has a pretty vertex. Note that no odd antihole of length at least seven contain a pretty vertex. Our main result is:

Theorem 1. Let G be a graph which has a pretty vertex ‘u such that no odd hole of G contains ‘u, and G - ‘u admits an w ( G - w)-coloring f . Then we can derive from f , through some bichromatic exchanges, an w(G)-coloring of G.

As a consequence we have:

Corollary. Every pretty graph G with no odd hole can be w(G)-colored in polynomial time.

Corollary. Every pretty graph with no odd hole is perfect.

We should remark that the conclusion of the first corollary is false (unless P = N P ) when the graph may contain odd holes. Indeed, finding an optimal coloring is an NP-hard problem in the class of triangle-free graphs [12], which is included in the class of pretty graphs.

A graph is called triangulated if it has no induced cycle of length at least four. Hajnal and Suranyi [ 101 and Berge [3] proved that triangulated graphs are perfect. We call a graph incomplete if it is not a clique. Dirac [7] proved that every incomplete triangulated graph has two nonadjacent simplicia1 vertices.

A graph is called i-triangulated if every odd cycle of length at least five has two non- crossing chords. It is easy to see that every triangulated graph and every bipartite graph is i-triangulated.

A clique-cutset in a connected graph G is a subset of vertices S such that G - S is not connected and S is a clique. Given k graphs GI, . . . , GI, with disjoint vertex-sets, the Join of these graphs is the graph obtained by adding all edges with endpoints in different G2’s. A graph is called clique-separable if every connected induced subgraph either has a clique-cutset or is of one among two basic types: (1 ) the join of a bipartite graph and a

SlMPLlClAL ELIMINATION ORDERINGS 205

clique; (2) the join of several edgeless graphs. Gallai [8] proved that every i-triangulated graph is clique-separable. We will prove:

Theorem 2. Every clique-separable graph is pretty.

2. TRIVIALLY PERFECT GRAPHS

Before presenting the proof of the new results, let us recall some useful facts about the structure of graphs with no P4 and no 2Kz. Equivalently one may look at their comple- ments, i.e., graphs with no induced P4 and C4. Such graphs are called trivially p e ~ e c t in [9]. Call a vertex u of a graph G universal if it is adjacent to all vertices of G - u. Call a vertex isolated if it has no neighbor. It is easily proved that in a connected trivially perfect graph any vertex of maximum degree is universal. Hence every connected trivially perfect graph has a universal vertex. This can be reformulated as follows:

Lemma 1. Let M be any subgraph of a P4-free and 2Kz-free graph. Then either M is the join of several graphs or M has an isolated vertex.

From the algorithmic point of view, we will use the algorithm in 161. This algorithm decides in linear time O ( m ) if any input graph with m edges is P4-free and, if yes, produces a tree representation of the graph, which we describe recursively as follows.

0 The leaves of the tree are the vertices of the graph and are unlabeled. 0 If the graph is disconnected, with components GI, . . . , Gk, the tree is obtained by

creating a 0-labeled root and by linking it to the roots of the trees that represent the graphs GI, . . . , GI,.

0 If the complement G of the graph is disconnected, with components G1 ) . . . , G k , the tree is obtained by creating a 1-labeled root and by linking it to the roots of the trees that represent the graphs G1 ) . . . ) GI,.

By a theorem of Seinsche [ 151, a graph is P4-free if and only if every induced subgraph with at least two vertices either is disconnected or its complement is disconnected. Hence the above tree is well defined and unique. Its size is O(n). Moreover, one can easily compute w ( G ) using the tree representation. Indeed, if the root is labeled 0, the graph is not connected and so w ( G ) = max(w(G1)). . . , ~ ( G I , ) } , where GI , . . . ) Gk are the connected components of G. If the root is labeled 1 then G is not connected, and so w(G) = w(G1) + . . . + w ( G k ) , where G I , . . . , G k are the connected components of G. So w ( G ) can be computed recursively, given the tree, in time O(n).

Now, for testing 2Kz-freeness, the following lemma will be useful.

Lemma 2. Let G be a P4-free graph and T the associated tree. Then G is 2K2-free if and only if, for every 0-node t in T, all children of t except maybe one are leaves of the tree.

Boo$ This is a mere reformulation of Lemma 1. I So we can first test if a graph is P4-free in linear time and, if it is, test again in linear

time if it is 2Kz-free. It then follows that we can decide easily if a given graph G is pretty, as follows. For

each vertex, test if its neighborhood is P4-free and 2K2-free. If some vertex u1 is pretty,

206 JOURNAL OF GRAPH THEORY

iterate the procedure with G - vl. If at step (i + 1) no pretty vertex can be found then the induced graph G - {vl , . . . , vi} certifies that G is not pretty. If on the contrary the procedure goes through the whole graph, then we obtain a labeling v1, v2, ~ . . , v, of the vertex-set of G, where v, is a pretty vertex of G - (211,. . . , viP1} for each i = 1,. . . , n. We will call this a pretty ordering. This procedure finds either a pretty ordering for G or a subgraph that admits no pretty vertex, in time O(n2m) if G has n vertices and m edges. Conversely, the existence of a pretty ordering is a certificate that G is pretty. Indeed, if H is any induced subgraph of G, and i is the smallest integer such that vi is a vertex of HI then it is easy to see that v, is a pretty vertex of H.

It also follows that we can easily compute the maximum clique size of a pretty graph. Indeed, if v is any vertex then w ( G ) = max{w(G - v), 1 + w(N(v ) ) } . When v is a pretty vertex then w ( N ( v ) ) can be computed using the tree representing N(v) . Hence, iterating this procedure along the pretty elimination ordering, we can find the value of w(G) as well as a clique of that size. Given the pretty ordering, the complexity of this procedure is n times the complexity of computing the maximum clique size of a P4-free graph, which is O(m) , hence it is O(mn).

3. THE PROOF OF THEOREM 1

Let G be a graph as in the assumption of Theorem 1 and let f be any w ( G - v)-coloring of G - 21. To simplify we write q = w ( G - v).

If one of the q colors used by f does not appear in N ( v ) then clearly w(G) = q; moreover, by assigning such a color to v we obtain a q-coloring of G.

If N ( v ) contains a q-clique then clearly w(G) = y + 1; moreover, by assigning a new color to v we obtain a q + 1-coloring of G.

In the remaining case, all the q colors appear in N ( v ) but N ( v ) contains no q-clique. We will use the following lemma (which is inspired by a similar argument due to Irena Rusu [14, p. 351).

Lemma 1. When all q colors appear in N(v) , and N(v) contains no q-clique, then there exist two colors S1, S2 such that there is no S1S2-edge in N ( v ) .

Proof. We prove this lemma by induction on q. The fact is trivial for q = 1,2. Now assume y 2 3. If N ( v ) is edgeless then the desired fact is again trivial. Now, let us assume that N ( v ) contains an edge. By Lemma 1, we can write N ( v ) = M u S, with M n S = 0, where S is a stable set of N ( v ) with no edge to M , and A4 is a join of several parts M I , . . . , Mk (with k 2 2). Note that !(Mi) n f ( M j ) = 0 for 1 5 i < j 5 k. We may assume that f(S) C f(M), for otherwise, if some color S1 is used in S and not in MI then S1, S2 is the desired pair for any color S, used in M.

Writeci =If(Mi)Jandqi=w(Mi)fori=l , . . . , I c . Clearlyc~Lyi. Wehaveel+.- .+ Ck = q, and q1 + ... + q k = w ( N ( v ) ) < q. Hence and by symmetry we may assume that q1 < el. Let G1 be the subgraph of G - ‘u induced by the vertices whose color is in f(M1). Note that w(G,) = cl, since any q-clique of G - v must have el vertices in GI. Hence the restriction of f to GI is an w(G1)-coloring of GI. Call G’ the subgraph of G induced by GI + v. Note that the neighborhood of v in G’ is MI u R1, where R1 is the subset of vertices of S whose color is in MI), and this neighborhood contains no el-clique. Since cI < q, we may apply the induction hypothesis to G’ and v, which is a pretty vertex of G’: since q1 < c1 , there exist in G’ two colors of the restriction of f with the desired property.

SlMPLlClAL ELIMINATION ORDERINGS 207

Clearly these two colors have the desired property for G itself. This concludes the proof of the lemma. 1

The lemma implies the existence of two color classes S1, S2 with no S1S2-edge in N ( v ) . In the bipartite graph induced by S1 u S2, let T be the union of all connected components containing at least one vertex of SlnN(w). It must be that S2nN(v)nT = 0, for otherwise there would exist in T, a shortest path P from a vertex in SlnN(v) to a vertex in S2nN(v), and then P + w would be an odd cycle, not a triangle (since N ( v ) contains no S1S2-edge), i.e., P + w would be an odd hole, contradicting the general hypothesis. Now we swap the colors 1 and 2 along T (“bichromatic exchange”). This yields a coloring of G - w such that there is no vertex of color 1 in N ( v ) ; hence we can assign this color to w and obtain

1 With this theorem we can color every pretty graph G with no odd hole using exactly

w(G) colors, by iterating the above procedure along a pretty elimination ordering. The complexity of this algorithm can be estimated as follows. Assume G has n vertices and m edges. Given the pretty vertex w, it takes O ( ~ ( V ) ~ ) to look for two colors S1, S2 with no &&-edge in N ( v ) , and O(m) to perform the bichromatic exchange if necessary. Iterating this for each vertex entails overall complexity O ( C , { ~ ( V ) ~ + m}) = O(mn).

a q-coloring of G. This completes the proof of the Theorem.

4. THE PROOF OF THEOREM 2

We will prove a lemma similar to Dirac’s [7].

Lemma 1. In an incomplete clique-separable graph, there exists a pair of non-adjacent pretty vertices.

ProoJ Let G be a clique-separable graph. We prove the lemma by induction on the number of vertices of G.

First assume that G is the join of a bipartite graph B and a clique. Observe that the neighborhood of any vertex from B is the join of a clique and a stable set, which is easily seen to be 2K2-free and P4-free. Since G is incomplete, there are two non-adjacent vertices in B. Then these two vertices form the desired pair.

Next, assume that G is the join of several edgeless graphs G I , . . . , Gk. The neighborhood of any vertex is the join of k - 1 of these edgeless graphs, which again is easily seen to be 2K2-free and P4-free. Since G is incomplete we may assume that G I has at least two vertices. Then any two vertices in G I form the desired pair.

Finally, assume that G has a clique cutset C. Let R 1 , . . . , Rk be the components of G - C, with k 2 2. For i = 1,2, the subgraph induced by R, U C either is a clique or has, by induction, two non-adjacent pretty vertices of which at least one, say xi, is necessarily in I&. If R, u C is a clique pick any 2, in R,. Then zl, 2 2 is the desired pair for G. 1

1 As a conclusion, we may want to compare pretty perfect graphs with other known

classes. It is easy to check that the line-graph of K3,3 - e is a pretty perfect graph; however it is neither in the class BIP’ defined in [5] nor in the class of quasi-parity graphs defined in [13] which contain most classical families of perfect graphs. On the other hand, some small perfect graphs are not pretty: for example the join of two P4’s, and the join

Now Theorem 2 follows immediately from Lemma 1.

of two 2K~’s. We leave as an open problem the recognition of pretty perfect graphs.

208 JOURNAL OF GRAPH THEORY

References

C. Berge, Les problemes de coloration en theorie des graphes, Publ. Inst. Stat. Univ. Paris, 9

C. Berge, Firbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind (Zusarn- rnenfassung), Wiss. Z. Martin Luther Univ. Math.-Natur. Reihe 10 (1961), 114-1 15. C. Berge, Graphs. North-Holland, Amsterdarn/New York, 1985. C. Berge and V. Chvatal, editors. Topics on perject graphs (Annals of Disc. Math. 21). North- Holland, Amsterdam (1984). V. Chvatal, Star-cutsets and perfect graphs, J. Comb. Theory B, 39 (1985), 189-199.

D. G. Corneil, Y. Perl, and L. K. Stewart, A linear recognition algorithm for cographs, SIAM J. Comput. 14 (1985), 92G934. G. A. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961), 71-76.

T. Gallai, Graphen mit triangulierbaren ungeraden Vielecken. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 7 (1962), 3-36. M. C . Golumbic, Trivially perfect graphs, Discrete Math., 24 (1978), 105-107.

A. Hajnal and J. Suranyi, Uber die Auflosung von Graphen in vollstandige Teilgraphen, Ann. Univ. Sc. Budapestinensis, 1 (1958), 11 3-121.

L. Lovasz, “Perfect graphs,” In Selected Topics in Graph Theory 2, L. W. Beineke and R. J. Wilson, editors, pp, 55-87. Academic Press, 1983. F. Maffray and M. Preissmann, A note on the NP-completeness of the k-colorability problem for triangle-free graphs, Discrete Math, in press.

H. Meyniel, A new property of critical imperfect graphs and some consequences, Eur. J. Com- binatorics, 8 (1987), 313-316.

I. Rusu, Graphes pa$aits: itude structurelle et algorithmes de coloration. PhD thesis, Univer- sity of Paris-Sud, Orsay (1 994). S. Seinsche, On a property of the class of n-colorable graphs, J. Comb. Theory B 16 (1974),

(1960), 123-160.

191-193.

Received November 10. 1995