***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Pierre Aboulker (ENS Paris)

Thursday 13th November, 3:00 in Fine Hall 224.

Title:  Clique number of tournaments

The dichromatic number of a directed graph D is the minimum integer k such that the 
vertex set of D can be partitioned into k acyclic subdigraphs. It is easy to see 
that the chromatic number of a graph G is the dichromatic number of the digraph 
obtained from G by replacing each edge with a digon (two anti-parallel arcs). Based 
on this simple observation, many theorems concerning the chromatic number of undirected 
graphs have been generalized to digraphs via dichromatic number. However, no concept 
analogous to clique number for digraphs has been available. The purpose of this
presentation is to explore such a concept and its relationship with the dichromatic 
number, mirroring the relationship between the clique number and the chromatic number in 
undirected graphs. We will focus, in particular, on studying the notion of χ-boundedness.

		----------------------------------

Anyone wishing to be added to or removed from the mailing list should
contact Paul Seymour (pds@math.princeton.edu)