A Semi-Strong Perfect Graph Conjecture

A Semi-Strong Perfect Graph Conjecture

Annals of Discrete Mathematics 21 (1984)279-280 @ Elsevier Science Publishers B.V. A SEMI-STRONG PERFECT GRAPH CONJECTURE v. CHVATAL School of Comp...

211KB Sizes 2 Downloads 31 Views

Annals of Discrete Mathematics 21 (1984)279-280 @ Elsevier Science Publishers B.V.

A SEMI-STRONG PERFECT GRAPH CONJECTURE

v. CHVATAL

School of Computer Science, McGill University, Montreal, Canada

A graph is called perfecr if, for each of its induced subgraphs F, the chromatic number of F equals the number of vertices of the largest clique in F. This notion has been introduced by Claude Berge [l], [ 2 ] , who proposed the following two conjectures: (1) a graph is perfect if and only if its complement is perfect, (2) a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five or to the complement of such a cycle. The first of these conjectures has been proved by Lovasz [3]; the second, known as the Strong Perfect Graph Conjecture, remains open. The purpose of this note is to interpose a new conjecture between (1) and (2). Let us say that a graph G has the P4-structure of a graph H if there is a bijection f between the set of vertices of G and the set of vertices of H such that a set S of four vertices in G induces the path P4of length three in G if and only if f ( S ) induces a P4in H. The conjecture interposed between (1) and (2) is: (1;) if G has the P4-structure of a perfect graph then G is perfect.

Trivially, (1;) implies (1); to show that (2) implies (l;), it will suffice to establish the following fact.

Theorem. The only graphs having the P4-structure of an odd cycle of length at least ,fiue are the cycle itself and its complement. Sketch of Proof. When the cycle has length five or seven, the assertion can be verified by an exhaustive search. Now let n be an integer greater than eight and let a graph G have the P4-structure of the cycle C, of length n. The vertices of G may be labeled as u , , u z r . .. , u. in such a way that, with the subscript arithmetic taken modulo n, a set S induces a P4 in G if and only if S = {?I,+,, u , + ~u, , + ~ , for some i. Now each subgraph G, of G induced by {a+,,u , + ~. ,. . , u , + ~has } the P4-structure of the path P8 of length seven. Further exhaustive search reveals that there are precisely four such graphs: P8itself, its complement p8,the graph F shown in Fig. 1, and its complement I? Now it is easy to verify that 279

v. Chvcitaf

280

Fig. 1

G, Pa implies G,,, = Pa, 2

-

G, = p, implies G,,, = Pa, G,

G,

2

I (

F implies G,+, = F,

P implies G,+, =E

In particular, if some G,is isomorphic to Pathen every G,is isomorphic to Pa.In this case, it is easy to verify that G is isomorphic to C.. Similarly, if some G,is isomorphic to pa then G is isomorphic to The remaining two options are excluded whenever n is odd: in this case, we would have G,,, = GI whenever k is odd, which is incompatible with G,,, = GI.

cn.

References [l] C.Berge, Fiirbung von Graphen deren samtliche bzw. ungerade Kreise starr sind (Zusammenfassung), Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Natur. Reihe (l%l), 114. [2] C . Berge, Sur me conjecture relative au problbme des codes optirnaux, Commun. 13ibme Assemblte Gtn. URSI, Tokyo (1%2). [3] L. Lovhz, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253-267 (this volume, pp. 29-42).