Irena Penev

Selected Chapters on Graph Theory - NDMI070 (winter 2018/2019)

Time and place
TBD

Course content
Graph decomposition and coloring. Perfect graphs, χ-bounded classes, clique-coloring.

Tentative schedule of lectures
Week 1. Introduction. Graphs of arbitrarily large girth and chromatic number.

Week 2. Perfect graphs 1: The (Weak) Perfect Graph Theorem.

Week 3. Perfect graphs 2: Cographs and weakly chordal graphs. Decompositions that cannot appear in minimal imperfect graphs.

Weeks 4-5. Perfect graphs 3: Bull-free perfect graphs. The Strong Perfect Graph Theorem and a (very, very brief) outline of its proof.

Weeks 6-7. Clique-coloring. Perfect graphs of arbitrarily large clique-chromatic number.

Week 8. χ-Bounded classes 1: Examples and decompositions that preserve χ-boundedness.

Weeks 9-10: χ-Bounded classes 2: Subdivisions of trees.

Week 11: χ-Bounded classes 2: Scott's conjecture and its counterexample.

Weeks 12-14: TBD

Literature
Lecture notes and journal articles, including the following:
G. Bacsó, S. Gravier, A. Gyárfás, M. Preissmann, and A. Sebő, "Coloring the maximal cliques of graphs", SIAM J. Discrete Math. 17 (3) (2004), 361-376.

P. Charbit, I. Penev, S. Thomassé, and N. Trotignon, "Perfect graphs of arbitrarily large clique-chromatic number," J. Combin. Theory Ser. B 116 (2016): 456-464.

V. Chvátal and N. Sbihi, "Bull-Free Berge Graphs Are Perfect," Graphs Combin. 3 (1987), 127-139.

Z. Dvořák and D. Kráľ, "Classes of graphs with small rank decompositions are χ-bounded," Eur. J. Combin. 33 (2012), 679-683.

R.B. Hayward, "Weakly triangulated graphs," J. Combin. Theory Ser. B 39 (1985), 200-209.

A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W.T. Trotter, B. Walczak, "Triangle-free intersection graphs of line segments with large chromatic number," J. Combin. Theory Ser. B 105 (2014), 6-10

A.D. Scott, "Induced trees in graphs of large chromatic number," J. Graph Theory 24 (1997), 297-311.

D. Seinsche, "On a property of the class of n-colorable graphs," J. Combin. Theory Ser. B 16 (2) (1974), 191-193.



Evaluation
The final grade will be based on weekly/biweekly homework and an oral exam.