10:30AM - 12:00PM

Institute of Mathematics (NTU Campus)

LECTURE1: PERFECTION AND BEYOND

ABSTRACT: About 10 years ago one of the central open problems in graph theory at the time, the Strong Perfect Graph Conjecture, was solved. The proof used structural graph theory methods, and spanned 155 journal pages. The speaker was part of the team of authors of this mathematical beast. In this talk we will explain the problem, describe some of the ideas of the proof (that has since been shortened somewhat), and discuss related problems that have been a subject of more recent research.

LECTURE2: INDUCED SUBGRAPHS AND CHROMATIC NUMBER

ABSTRACT: The Strong Perfect Graph Theorem provides a structural description of all graphs that behave particularly well with respect to coloring in terms of their forbidden induced subgraphs. In the 1980s Andras Gyarfas made three beautiful conjectures, generalizing the idea of perfect graphs, by suggesting a more relaxed definition of what "behaving well" means. All three of these conjectures have recently been solved. In this talk we will discuss the conjectures and their proof ideas.

LECTURE3: INDUCED SUBGRAPHS AND COLORING ALGORITHMS

ABSTRACT: The problem of testing if a graph can be colored with a given number k of colors is NP-complete for every k>2. But what if we have more information about the input graph, namely that some fixed graph H is not present in it as an induced subgraph? It is known that the problem remains NP-complete even for k=3, unless H is the disjoint union of paths. We consider the following two questions:

1. For which graphs H is there a polynomial time algorithm to 3-color (or in general k-color) an H-free graph?

2. For which graphs H are there finitely many 4-critical H-free graphs?

This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.

### 許振榮先生

### 許振榮講座