### perfect graph terms

**clique**
set of pairwise adjacent vertices

**stable **
set of pairwise non-adjacent vertices
(a.k.a. stable set, independent set)

**cliquesize ω(G)**
size of largest clique of G

**stablesize α(G)**
size of largest stable of G

**chromatic number χ(G)**
minimum number of colours needed to colour vertices of G
so that adjacent vertices get different colours;
equiv: min'm number of stables needed to cover vertices
(a.k.a. stable cover number)

**clique cover number θ(G)**
minimum number of cliques needed to cover vertices

**some min/max inequalities**

χ(G) ≥ ω(G)

θ(G) ≥ α(G)

**induced subgraph**
subgraph induced by a vertex subset (a.k.a. vertex induced subgraph)

**perfect**
graph G with χ(H)=ω(H)
for each induced subgraph H of G

**Ck**
induced cycle with k vertices

**hole**
induced subgraph isomorphic to Ck with k at least four

**antihole**
induced subgraph isomorphic to Ck-complement
with k at least four

**Berge**
graph with no odd hole and no odd antihole

**WPGC**
weak perfect graph conjecture, Berge 1960:
graph perfect iff complement perfect

(proved by Lovasz 1971, now called perfect graph theorem)

**SPGC**
strong perfect graph conjecture, Berge 1960:
graph perfect iff graph Berge

(proved by Chudnovsky/Robertson/Seymour/Thomas 2002;
now called strong perfect graph theorem)

**line graph of G**
graph E(G) whose vertices are edges of G, with

edge adjacency in G corresponding to vertex adjacency in E(G)

**Pk**
induced path with k vertices

**some perfect graph classes**

**bipartite**
trivial or vertices can be partitioned into two stables;

equiv: χ(G) at most two

**line graphs of bipartite graphs**

**interval**
intersection graph of intervals on a line

(interval iff chordal and co-comparability)
**comparability**
edge set is transitively orientatable

**chordal**
no hole

**cograph**
every nontrivial
induced subgraph disconnected or co-disconnected

(cograph iff no P4)
**weakly chordal**
no long hole (Ck with k at least 5) in graph or complement

**perfectly orderable**
admits a linear vertex order < yielding

no ``bad P4''
(P4 with edges ab,bc,cd and a < b and d < c)