List of speakers

- 11AM-12PM Tomáš Kaiser (University of West Bohemia, Czech Republic) : Applications of the matroid-complex intersection theorem
- 1:30PM-2:30PM Paul Seymour (Princeton University, USA) : Graphs, Tournaments, Colouring and Containment
- 2:45PM-3:45PM Maria Chudnovsky (Columbia University, USA) : Excluding paths and antipaths
- 4:30PM-5:30PM Daniel Kráľ (University of Warwick, UK) : Quasirandomness and property testing of permutations
**(Colloquium)**

*heroes*; they have the property that all tournaments not containing H as a subtournament have bounded chromatic number (colouring a tournament means partitioning its vertex-set into transitive subsets). In joint work with eight authors, we found all heroes explicitly. That was great fun, and it would be nice to find an analogue for graphs instead of tournaments.

The problem is too trivial for graphs, if we only exclude one graph H; but it becomes fun again if we exclude a finite set of graphs. The Gyarfas-Sumner conjecture says that if we exclude a forest and a clique then chromatic number is bounded. So what other combinations of excluded subgraphs will give bounded chromatic (or cochromatic) number? It turns out (assuming the Gyarfas-Sumner conjecture) that for any finite set S of graphs, the graphs not containing any member of S all have bounded cochromatic number if and only if S contains a complete multipartite graph, the complement of a complete multipartite graph, a forest, and the complement of a forest.

Proving this led us to the following: for every complete multipartite graph H, and every disjoint union of cliques J, there is a number n with the following property. For every graph G, if G contains neither of H,J as an induced subgraph, then V(G) can be partitioned into two sets such that the first contains no n-vertex clique and the second no n-vertex stable set.

In turn, this led us (with Alex Scott) to the following stronger result. Let H be the disjoint union of H_1,H_2, and let J be obtained from the disjoint union of J_1,J_2 by making every vertex of J_1 adjacent to every vertex of J_2. Then there is a number n such that for every graph G containing neither of H,J as an induced subgraph, V(G) can be partitioned into n sets such that for each of them, say X, one of H_1,H_2,J_1,J_2 is not contained in G|X.

How about a tournament analogue of this? It exists, and the same (short) proof works; and this leads to a short proof of the most difficult result of the heroes paper that we started with.

There are a number of other related results and open questions. Joint work with Maria Chudnovsky.

The results in this talk were obtained jointly with Tereza Klimosova or Oleg Pikhurko.