A pair of vertices (x, y) of a graph G is called an ω-critical pair if ω(G + x y)>ω(G), where G + x y denotes the graph obtained by adding the edge x y to G and ω(H) is the clique number of H. The ω-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S meets every ω-clique of G, and ω-critical pairs within S form a connected graph. In 1993, G. Bacsó conjectured that if G is a uniquely ω-colorable perfect graph, then G has at least one forced color class. This conjecture is called the bold conjecture, and implies the strong perfect graph theorem. However, a counterexample of the conjecture was subsequently found by Sakuma.

clique number | strong perfect graph theorem