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).