F
is defined as
the smallest number of colors that can be assigned to vertices of
F
in such a way that every two adjacent vertices receive
two distinct colors; the clique number of F
is
defined as the largest number of pairwise adjacent vetices in
F
. Trivially, the chromatic number of every graph is at least its
clique number. A graph G
is called perfect if,
for each of its induced subgraphs F
, the chromatic number
of F
equals the largest number of pairwise adjacent
vetices in F
.
A hole is a chordless cycle of length at least four; an
antihole is the complement of such a cycle; holes and
antiholes are odd or even according to the parity
of their number of vertices. No odd hole is perfect (the clique
number of an odd hole is 2
and its chromatic number is
3
) and no odd antihole is perfect (the clique number
of an antihole with 2k+1
vertices is k
and its
chromatic number is k+1
).
In 1960, Claude Berge
announced the conjecture that a graph is perfect if (and only if)
it contains no odd hole and no odd antihole. This conjecture became
known as the Strong Perfect Graph Conjecture. Its early
history has been described by Berge and
Ramírez-Alfonsín.
Chvátal and Sbihi proposed calling a
graph a Berge graph if it contains no odd hole and no odd
antihole. In this terminology, the Strong Perfect Graph Conjecture
asserts that a graph is perfect if (and only if) it is a Berge
graph.
every square-free Berge graph -- meaning Berge graph containing no hole of length four --either belongs to one of two basic classes (bipartite graphs and line-graphs of bipartite graphs), or else it has one of two structural faults (star-cutset or 2-join);since bipartite graphs and line-graphs of bipartite graphs are perfect and since minimal imperfect Berge graphs have neither of the two structural faults; it follows that every square-free Berge graph is perfect.
every Berge graph either belongs to one of five basic classes, namely,since all graphs in the five basic classes graphs are perfect, since minimal imperfect Berge graphs have neither of the first three structural faults and since -- as Chudnovsky, Robertson, Seymour, and Thomas also prove in their 148-page paper -- an imperfect Berge graph with the smallest number of vertices has no balanced skew partition, it follows that every Berge graph is perfect.or else it has one of four structural faults, namely,
- bipartite graphs,
- complements of bipartite graphs,
- line-graphs of bipartite graphs,
- complements of line-graphs of bipartite graphs,
- "double split graphs",
- 2-join,
- 2-join in the complement,
- M-join,
- a balanced skew partition;
Since all double split graphs are easily seen to admit skew partitions (even though only rarely balanced skew partitions), an easy corollary of the structural theorem asserts that
every Berge graph either belongs to one of four basic classes, namely,Furthermore, Maria Chudnovsky (Berge Trigraphs, Journal of Graph Theory 53 (2006), 1--55) showed that an even stronger asertion remains valid: M-joins can be dropped.or else it has one of four structural faults, namely,
- bipartite graphs,
- complements of bipartite graphs,
- line-graphs of bipartite graphs,
- complements of line-graphs of bipartite graphs,
- 2-join,
- 2-join in the complement,
- M-join,
- a skew partition.
C. Berge and J.L. Ramírez-Alfonsín, Origins and
genesis, in: Perfect Graphs
(J.L. Ramírez-Alfonsín and B.A. Reed, eds.), Wiley,
2001, pp. 1--12.
M. Burlet and J.-P. Uhry, Parity graphs, in: Topics
on perfect graphs (C. Berge and V. Chvátal, eds.)
North-Holland Mathematics Studies, 88. Annals of Discrete Mathematics,
21. North-Holland Publishing Co., Amsterdam-New York, 1984,
pp. 253--277
M. Chudnovsky, N. Robertson, P.D. Seymour, and R.Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51--229
V. Chvátal, Star-cutsets and perfect graphs,
J. Combin. Theory Ser. B 39 (1985), 189--199.
M. Conforti, G. Cornuéjols, and
K. Vušković, Square-Free
Perfect Graphs, J. Combin. Theory Ser. B 90
(2004), 257--307.
L. Lovász, Normal hypergraphs and the perfect graph conjecture
, Discrete Math. 2 (1972), 253--267.
P.D. Seymour, Decomposition of regular matroids, J. Combin. Theory Ser. B 28 (1980), 305--359.
Related pages: