Irena Penev

Topics in Structural Graph Theory and Algorithms - NDMI105 (summer 2022)

Time and place
Thursday, 14:00-15:30, S1

Course content
Forbidden induced subgraphs and graph decompositions. Chordal graphs and Lexicographic Breadth-First-Search (LexBFS). Clique-cutsets and algorithmic applications. Universally signable graphs. Detecting odd holes (and recognition of perfect graphs). Perfect graphs and χ-bounded classes.

Tentative schedule of lectures
Week 1. Chordal graphs.

Week 2. Universally signable graphs.

Week 3-5. Lexicographic Breadth-First-Search (LexBFS), clique-cutsets, and algorithmic applications.

Week 6. Perfect graphs and χ-bounded classes.

Weeks 7-8. Graphs without long and odd cycles.

Week 9. A counterexample to Esperet's conjecture.

Weeks 10-11. Detecting odd holes.

Weeks 12-14. TBD

Lecture notes and journal articles, including the following:
A. Carbonero, P. Hompe, B. Moore, S. Spirkl, "A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number", arXiv:2201.08204.

M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, "Detecting an odd hole", JACM 67 (2020), Article 5.

M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, "Universally signable graphs", Combinatorica 17 (1) (1997), 67-77.

A. Gyárfás, "Problems from the world surrounding perfect graphs", Zastosowania Matematyki - Applicationes Mathematicae XIX(3-4) (1987), 413-441.

D.J. Rose, R.E. Tarjan, and G.S. Lueker, "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing 5 (1976), 266-283.

A. Scott, "Induced cycles and chromatic number", Journal of Combinatorial Theory Series B 76 (1999), 150-154.

R. Tarjan, "Decomposition by clique separators", Discrete Mathematics 55 (1985), 221-232.

The final grade will be based on a 90 minute presentation of one research paper.