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