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)