Bold Conjecture

A pair of vertices  of a graph  is called an -critical pair if , where  denotes the graph obtained by adding the edge  to  and  is the clique number of . The -critical pairs are never edges in . A maximal stable set  of  is called a forced color class of  if  meets every -clique of , and -critical pairs within  form a connected graph.

In 1993, G. Bacsó conjectured that if  is a uniquely -colorable perfect graph, then  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 (1997).

REFERENCES

Sakuma, T. "A Counterexample to the Bold Conjecture." J. Graph Th. 25, 165-168, 1997.Sebő, A. "On Critical Edges in Minimal Perfect Graphs." J. Combin. Th. B 67, 62-85, 1996.