BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Combinatorics and Probability Seminar
SUMMARY:Online graph coloring with bichromatic exchanges -
Marc Heinrich (Université Lyon 1)
DTSTART:20180613T140000Z
DTEND:20180613T150000Z
UID:TALK3187AT
URL:/talk/index/3187
DESCRIPTION:Greedy algorithms for the graph coloring problem r
equire a large number of\ncolors\, even for very s
imple classes of graphs. For example\, any greedy\
nalgorithm coloring trees requires $\\Omega(\\log
n)$ colors in the worst case.\nWe consider a varia
tion of the First-Fit algorithm in which the algor
ithm is\nallowed to make modifications to previous
ly colored vertices by performing\nlocal bichromat
ic exchanges. We show that such algorithms can be
used to find an optimal coloring in the case of bi
partite graphs\, chordal graphs and\nouterplanar g
raphs. We also show that it can find coloring of g
eneral planar\ngraphs with $O(\\log \\Delta)$ colo
rs\, where$\\Delta$ is the maximum degree of\nthe
graph. The question of whether planar graphs can b
e colored by an online algorithm with bichromatic
exchanges using only a constant number of colors i
s still open. \nThis is a joint work with Sylvain
Gravier.\n\n
LOCATION:Watson LTA
CONTACT:Allan Lo
END:VEVENT
END:VCALENDAR