University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Correspondence Coloring and its Applications

Correspondence Coloring and its Applications

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

  • UserLuke Postle (University of Waterloo)
  • ClockFriday 10 November 2017, 14:00-15:00
  • HouseWatson 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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.