Forced color classes, intersection graphs and the strong perfect graph conjecture
In 1996, A. Sebo[11] raised the following two conjectures concerned with the famous Strong Perfect Graph Conjecture: (1) Suppose that a minimally imperfect graph G has a vertex p incident to 2 omega(G)-2 determined edges and that its complement (G) over bar has a vertex q incident to 2 alpha(G) - 2 determined edges. (An edge of G is called deter mined if an omega-clique of G contains both of its endpoints.) Then G is an odd hole or an odd antihole. (2) Let nu(0) be a vertex of a partitionable graph G. And suppose A,B to be omega-cliques of G so that nu(0) is an element of A boolean AND B. If every omega-clique K containing the vertex v(0) is contained in A boolean OR B, then G is an odd hole or an and antihole. In this paper, we will prove (1) for a minimally imperfect graph G such that (p,q) is a determined edge of either G or (G) over bar, and prove (2) for a minimally imperfect graph G such that (G) over bar is C-4-free and edges of (G) over bar are all determined edges. (C) 2000 Elsevier Science B.V. All rights reserved.
forced color class the strong perfect graph conjecture minimally imperfect graphs