Bold Conjecture

A pair of vertices (x,y) of a graph G is called an omega-critical pair if omega(G+xy)>omega(G), where G+xy denotes the graph obtained by adding the edge xy to G and omega(H) is the clique number of H. The omega-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 omega-clique of G, and omega-critical pairs within S form a connected graph.

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

See also

Clique Number, Strong Perfect Graph Theorem

Explore with Wolfram|Alpha


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.

Referenced on Wolfram|Alpha

Bold Conjecture

Cite this as:

Weisstein, Eric W. "Bold Conjecture." From MathWorld--A Wolfram Web Resource.

Subject classifications