Course MAT579

Topics in Discrete Mathematics: Coloring and induced subgraphs

There are several well-known open questions about the coloring properties of graphs with certain induced subgraphs forbidden, for instance:

1.  Erdos-Hajnal conjecture - for every graph H, there exists c>0 such that every n-vertex graph not containing H as an induced subgraph has a clique or stable set with at least O(n^c) vertices.

2.  Gjarfas conjecture - for every integer k>0, there exists c>0 such that every graph with no clique of size k and no odd cycle of length >3 as an induced subgraph has chromatic number at most c.

3.  Gyarfas-Sumner conjecture - for every integer k>0 and every forest F, there exists c such that every graph with no clique of size k and not cointaining F as an induced subgraph has chromatic number at most c.

The aim of this course is to survey what is known about these conjectures, and discuss some analogous results and conjectures for tournaments.

First Meeting:  February 5