Correspondence Coloring and its Applications

Add to your list(s) Download to your calendar using vCal

• Luke Postle (University of Waterloo)
• Friday 10 November 2017, 14:00-15:00
• Watson LTC.

If you have a question about this talk, please contact Guillem Perarnau.

Correspondence coloring, introduced by Dvorak and I in 2015, is a generalization of list coloring wherein vertices are given lists of colors and each edge is given a matching between the lists of its endpoints. So unlike in list or even ordinary coloring where adjacent vertices are not allowed to be colored the same, here we require that the colors of adjacent vertices are not matched along the edge. In this manner, correspondence coloring is list coloring where the ‘meaning’ of color is a local rather than global notion. Although results for correspondence coloring are interesting in their own right, in this talk we will focus on applying correspondence coloring to difficult problems from coloring and list-coloring to obtain new results; for example, for 3-list-coloring planar graphs without 4 to 8 cycles (joint work with Dvorak), on Reed’s conjecture (joint work with Bonamy and Perrett) and on the list coloring version of Reed’s conjecture (joint work with Delcourt).

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTC

Note that ex-directory lists are not shown.