On the strong perfect graph conjecture and critical graphs

On the strong perfect graph conjecture and critical graphs

Discrete Mathematiti 41 (1982) lOl-104 North-Holland Publishing Company and Department of Matkmatics, Received 22 September Revised 22 May 1981 101 ...

356KB Sizes 3 Downloads 46 Views

Discrete Mathematiti 41 (1982) lOl-104 North-Holland Publishing Company

and Department of Matkmatics, Received 22 September Revised 22 May 1981



Indian Institute of Technology Kanpur 208016, India )


In this paper we obtain some propc: d:,:s of graphs which xe critical with respect to perfectness. Some alternate forms of Berge’s 123strong perfc:ct graph conjecture are als0 given.

We refer to [2] for the basic definitions and adopt the notation and terminology give? in [a]. A graph G is perfect if TV(H) = 9( ) c.equivalently 00 = x(H); see the following Remark) for every induced sub h I-&of (3. A graph C; is critical if G is not perfect and G - v is perfect fclr every v E V(G). A hole is a chordless odd circuit C2k+l, k 2 2 and an antihole is the complement of a hole.

. By a well-known

result of Lov&z [S], a praph G is plerfect ifx its complement e is perfect. Thus a graph G is critical iff (? is critical: this enables duality arguments to be used. y standard


we obtain.

e For critical graphs, 8 = ux+ I and x = w + I. For v E V(C), let set of all vertices respectively. For critical graphs G,

M. R. Sridhcoran,0.T. George


According to [3, p. 3811 or [7, p. M], O(H,(u)) - PL(N~(u)) = UY - I, thus, by Lemmma 1, (iii) and (iv) hold. (i) and (ii) follow from (iii) :md (iv), al:plied to G, by dualizat ion. .

For v&id


2( n - 11”* c w + my< $(n - 3), where n = \ V(G ,I_

. For a critical graph G, 20 - 2~ d(u) c n - 2cx + 1 for all u E V(G) (see, e.g., [3, p. 381] or [7, p. 1561); hence o -t-a <$(rr t 3). By [4], wcu= n - 1. Now the lower bound for o + CYis obtained by observi,!g that whenever the product of two positive numbers is constant, say k, then their sum is minimum when each number is I?‘*. ence w +(x 3 2(n - l)‘l’.

2. For critical graphs, 2 < o), Q 5~$(n - 1). For later use, we quote Theorem 9 of [.4]: (A) If G has no holes or antiholes and w(G) = 3, then G is perfect. Lc& q be an odd prime or q ==9 and let n*=q+l graph G with n* vertices cannot be critical.

or n”‘=3q+l.


Assume that G is critical. From wu z dg - 1 [4] we obtain OKY= q or 3q. Since *w,cy3 2, the first case is possible only for q -7 9 and in either case w(G) = 3 or a(G) = OJ(@ = 3. G and G have an even number of vertices an1 are critical, neither of them contains a hole or an antihole as an induced subgraph. Wence, by (A), G or G is perfect, contradicting the hypothesis that G is critkal. . A critical

graph of eve;Jzortier cannot have less than 2 5 uertices.

. For a critical

graph G of euen order n, 5 s w, Q s $
Since 0(x = n - 1, o and (Yare odd, hence COa 3 and cy= o([email protected] a 3. G and G ard critical and have no holes or antiholes, therefore, by (A), o(G) = 3 and W(G) = 3. so 0 - 5 and ca!= 5, and the result fohows using ocy = YE - 1. Let ~11and n2 be the order of H,(u) and F&(Y), respectively. For a critical graph G, 2 s nl, a2 S n - 3.

ff:. o(G)a2,

o(G);s2, hence ~~~--di6,2))~2to(G)-22~2 and )-2322. Now t e result follows frsm n, + a2 = n -- 1. r a critical graph G


On the strong pafect graph conjecture and critictzl graphs


If the sum of two positive numbers x and y is a constan:, say k, ancI if their heir product x . y =$(k*-d*! difFe&cc: is d, the is maximum when d=:O that iswhenx=y=$k. ence the maximum value of xy is br(‘. The minimum value is attained when d is maximum, that is, by Lemma 3, when one nclmber is 2 aml the other is r;!- 3. If a graph G is critical and &-free, r all 2;’E V(G).

then o(H2(u)) = 2 ana’ d(v) =

G is &s-free, hence H*(v) cannot contain a triangle. Thcrrefore, w (E&(v)) s 2. But H*(v) is a connected graph [3] having at least two vertices (Lemma 3). This implies that u(&(v)) = 2. Since a(H2(v)) = cy-- 1, applying LovBsz’ characterization of perfect graphs [6], 2 (CX - 1) 3 ~1~= d(t?, II). But from the proof of Lemma 3, (G, c) 3 2,a - 2. Hence ai22= 2a - 2. Therefore, d(v) = t tzi= n -l--n*=n--2cn .



of Theorem

2 we obtain

If a graph G is critical and &,-free,

then cr(H,(v)) = 2 and d(v) =


The latest version of Berge’s conjecture is that a graph is perfect iti it does not contain &+i, or &+r, k 3 2 :LSan induced subgraph. This is equivalent to the statement that a critical graph is9CZk 1, or C2k+ 1, k 2 2. For a critical graph G, w + ar = $(n -t-3). Combining o + cy=&2+3) with oa!=n-1, we have 0=2 or 0=&z--1). If 0 L-2, then G is C2k+i, k 22 [3], and if w =$(n - l), then cy= 2; SQ G is C2k+l, k 2: 2 [4]. .

For a critical graph G, cr(H,(v)) = 2 for all u E V(

r a critical gra for all v E V(G).

(VI) = 2

M.R. Sridharan, 0.T. George


Combining nl 0n2 = 2:(~t-3) with n, + 112= n - 1, we obtain ytl =2 n1 ==2 implies 2’22a) -2, hence o =2. So G &+1, k 32 w. is &.,, k 22 [ then n-3Qz+ 1-2~ Therefore, a =2 and .

‘The number


of ed:ges in a critical graph

or II -3.

G is IZZCY +3-

f true, lhen e(G)= nw,+3-~(w+cY) and e(e)= no+3-2(~+a), NCI) = fr;-(n-l)=e(G)+e(@=(n-~)(w+cu)+~. The value y1= 4 is inadmissable This gi\ es n =4 or n==2(~++)-3. nc critical graph on 4 vertices. Hence o + (I[=&z + 3)”

therefore as there is

[ 13 A. Tucker, Critical perfect graphs and perfect 3-chromatic graphs, J. Combin. “heory (B) 23 ! 1977) lil3-149. [2] C. Berge, Soma: classes of perfect graphs, in: Graph Theory and Theoretical Physics (Academic Press, London/New York, 1967). 133 H. Sachs, On the Berge conjecture concerning perfect graphs, in: Combinatorial Structures and their Applicatisns (Gordon and Breach, New York, 1969) 377-384. [4] K.R. Parthasarathy and G. Ravindra, The strong perfect graph conjecture is trut3 for K,,,-free graphs, J. Combin. Theory (B) 21 (1976) 212-223. [_‘I]L. Lo&z, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253-267. [o] L. Lov;isz. A characterization of perfect graphs, J. Combin. Theory (B) 13 (19721 95-98. [7] E. Olaru, BeitrHge zur Theorie dans perfeIten Graphen, Elektronische Informaticnsverarbeitung und Kybernetik (EIK) 8 (1972) 147-172.