CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graph Colouring, Part II
Org: Michelle Delcourt (University of Illinois at Urbana-Champaign)

ANTON BERNSHTEYN, University of Illinois at Urbana-Champaign
Dirac's theorem for DP-critical graphs  [PDF]

Correspondence coloring, or DP-coloring, is a generalization of list coloring introduced recently by Dvo\v{r}\'{a}k and Postle. I will talk about a version of Dirac’s theorem on the minimum number of edges in critical graphs in the framework of DP-colorings. A corollary of this result is a solution to the problem, posed by Kostochka and Stiebitz, of classifying list-critical graphs that satisfy Dirac’s bound with equality. This is joint work with Alexandr Kostochka.

VIDA DUJMOVIC, University of Ottawa
Layered tree-compositions and graph colouring  [PDF]

Layered tree-decompositions are recently introduced generalizations of tree-decompositions. I will show how they can be used to obtain new results on couple of group colouring problems on proper minor closed families of graphs and beyond.

ARARAT HARUTYUNYAN, University of Toulouse
Coloring dense digraphs  [PDF]

The chromatic number of a digraph D is the minimum number of acyclic subdigraphs covering the vertex set of D. A tournament H is a hero if every H-free tournament T has bounded chromatic number as a function of H. Motivated by the Erdös–Hajnal conjecture, Berger et al. fully characterized the class of heroes in 2013. A simple digraph H is said to be a superhero if every H-free simple digraph D has chromatic number bounded as a function of H and $\alpha(D)$, the independence number of the underlying graph of D. We prove that a digraph is a superhero if and only if it is a hero, hence characterizing all superheroes. This answers a question of P. Aboulker. Based on joint work with T.-N. Le, A. Newman and S. Thomassé.

LUKE POSTLE, University of Waterloo
List Coloring with Requests  [PDF]

If a graph $G$ is $L$-colorable, how robust is the set of $L$-colorings? One approach to this question as studied by Thomassen and many others is to ask whether $G$ has exponentially many $L$-colorings. Here we introduce and investigate a different approach. We say $G$ is $\varepsilon$-flexible with respect to a list assignment $L$ if for every partial (not necessarily proper) $L$-coloring $\phi$ of $G$, there exists a proper $L$-coloring $\phi'$ of G which agrees with $\phi$ on at least an $\varepsilon$-fraction of its support. This is joint work with Zdenek Dvorak and Sergey Norin.

HEHUI WU, Shanghai Center for Mathematical Sciences
Digraphs coloring and tournaments with large domination number  [PDF]

A proper coloring of a digraph is a vertex coloring with no monochromatic directed cycle.

Erd\H{o}s and Neumann-Lara conjectured that if a undirected graph has large chromatic number, so does one of its orientaion. With Bojan Mohar, we proved the fractional version.

Recently, with Ararat Harutyunyan, Tien-Nam Le, St\'{e}phan Thomass\'{e}, we show that if the domination number of a Tournament is large, then so does one subtournament of bounded size. This verifies a conjecture of Berger et al: If the out-neighborhood of each vertex of a tournament has bounded chromatic number, so does the whole tournament.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology