Kdy a kde:

Odprednesena latka a plan prednasek:

DatumObsah prednaskyZdroje
11.10.,18.10. Perfektni grafy -- uvod, zakladni vlastnosti, algoritmus pro barveni, struktura (formulace) a z ni plynouci dukaz silne vety o p.g. (1),(2),(3),(4)
25.10 Struktura perfektnich grafu -- naznak dukazu. (2),(5),(6)
1.11. Referat -- stredne silna veta o perfektnich grafech.  
8.11. Referat -- algoritmus pro rozpoznavani perfektnich grafu.  
15.11. Zakazane podgrafy vynucujici skoro perfektnost.  
22.11. Odpada.  
29.11. Referat -- grafy bez indukovaneho podrozdeleni stromu jsou skoro perfektni.  
6.12. Struktura claw-free grafu, aplikace.  
13.12. Erdos-Hajnalova hypoteza -- formulace, motivace, zakladni vysledky.  
20.12. Referat -- Erdos-Hajnalova hypoteza pro grafy bez byka.  
3.1. Referat -- struktura bull-free grafu.  
10.1. Referat -- ???.  

Doporucena literatura:

  1. Gartner, Matousek: Approximation Algorithms and Semidefinite Programming, Springer, 2012, sections 3.3, 3.6, 3.7.
  2. Chudnovsky, Robertson, Seymour, Thomas: The strong perfect graph theorem, Annals of Mathematics (2006), 51-229.
  3. Cornuejols, Cunningham: Compositions for perfect graphs, Discrete Mathematics 55 (1985), 245-254.
  4. Conforti, Cornuejols, Gasparyan, Vuskovic: Perfect graphs, partitionable graphs and cutsets, Combinatorica 22 (2002), 19-33.
  5. Seymour: How the proof of the strong perfect graph conjecture was found.
  6. Roussel, Rubio: About skew partitions in minimal imperfect graphs, J. Combinatorial Theory, Ser. B 83 (2001), 171-190.