CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Graph Colouring, Part I
Org: Luke Postle (University of Waterloo)

MICHELLE DELCOURT, University of Illinois at Urbana-Champaign
On the List Coloring Version of Reed's Conjecture  [PDF]

Reed conjectured in 1998 the chromatic number of a graph should be at most halfway between clique number (trivial lower bound) and maximum degree plus one (trivial upper bound); Reed proved it is at most some convex combination of these quantities. Last year, Bonamy, Perrett, and Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Using new techniques, we show the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. Thus, 1/13 suffices for ordinary chromatic number. This is joint work with Luke Postle.

THOMAS KELLY, University of Waterloo
Beyond Degree-Choosability Toward a Local Epsilon Version of Reed's $\omega, \Delta, \chi$ conjecture  [PDF]

In 1998, Reed conjectured that every graph $G$ satisfies $\chi(G)\leq\lceil \frac{1}{2}(\Delta(G)+1+\omega(v))\rceil$, significantly strengthening Brooks' Theorem. In 1979, Erdős, Rubin, and Taylor proved that a graph $G$ is degree-choosable, meaning $G$ is $L$-colorable for every list-assignment $L$ satisfying $|L(v)|\geq d(v)$ for all $v\in V(G)$, unless every block of $G$ is a clique or odd cycle. We ask if every graph $G$ is $L$-colorable for every list-assignment $L$ satisfying $|L(v)| \geq \lceil\frac{1}{2}(d(v)+1+\omega(v))\rceil$, where $\omega(v)=\omega(G[N(v)\cup\{v\}])$. We prove this is true instead when $|L(v)|$ is some convex combination of $d(v)+1$ and $\omega(v)$, under certain mild assumptions.

Joint work with Luke Postle.

SOPHIE SPIRKL, Princeton University
Even Pairs and Prism Corners in Perfect Graphs  [PDF]

An even pair in a graph is a pair of vertices such that every induced path between them has an even number of edges. If $u$ and $v$ are an even pair in a perfect graph $G$, then $\chi(G/uv) = \chi(G)$, which makes even pairs useful for coloring.

I will show that a perfect graph which contains neither a 4-cycle nor a line graph of a bipartite subdivision of $K_4$ as an induced subgraph either is a complete graph or has an even pair.

Joint work with Maria Chudnovsky, Fr\'ed\'eric Maffray, and Paul Seymour.

DAVID WOOD, Monash University
Defective colouring of graphs excluding a subgraph or minor  [PDF]

Archdeacon (1987) proved that graphs on a fixed surface can be 3-coloured using colour classes inducing subgraphs of bounded maximum degree. Edwards, et al. (2015) showed that graphs with no $K_{t+1}$-minor have $t$-colourings with bounded max degree subgraphs. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This leads to new defective colouring results for graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter. Joint work with Patrice Ossona de Mendez and Sang-il Oum.

YELENA YUDITSKY, McGill University
Gyárfás-Sumner Conjecture Is Almost Always True  [PDF]

Gyárfás and Sumner conjectured independently in the 80’s that for every tree $T$, there is a function $f$ such that every $T$-free graph $G$ (i.e. graph without $T$ as an induced subgraph) whose largest clique has size $\omega(G)$, has chromatic number at most $f(\omega(G))$. We show that almost every $T$-free $G$ has chromatic number at most $(1+o(1))\omega(G)$ and that for most trees $T$ almost every $T$-free $G$, satisfies $\chi(G)=\omega(G)$. Key to doing so is a structural characterization of almost all $T$-free graphs.

Joint work with Bruce Reed.


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