 français conference home canadam home

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

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.