BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//LORIA - ECPv4.9.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:LORIA
X-ORIGINAL-URL:http://www.loria.fr
X-WR-CALDESC:Events for LORIA
BEGIN:VEVENT
DTSTART;TZID=UTC+1:20161005T150000
DTEND;TZID=UTC+1:20161005T160000
DTSTAMP:20190525T193635
CREATED:20160926T071359Z
LAST-MODIFIED:20160926T071359Z
UID:2778-1475679600-1475683200@www.loria.fr
SUMMARY:MALOTEC Seminar
DESCRIPTION:The first MALOTEC seminar of the season will take place on Wednesday\, October 5th\, from 3PM to 4PM in room B013. \nFrançois Pirot will give a presentation entitled “The bounds for the distance-t chromatic number\, and the effect of removing cycles”. \n \nAbstract : It is well known that you can colour a graph G of maximum degree D greedily with D+1 colors. Moreover\, this bound is tight\, since it is reached for example by the cliques. Johansson proved with a pseudo-random colouring scheme that you can colour triangle-free graphs of maximum degree D with no more than O(D/log D) colours. This is tight up to a multiplicative constant\, since you can pseudo-randomly construct a family of graphs of maximum degree D\, arbitrary large girth\, and chromatic number bigger than c D/log D\, for some constant c. \nWhen you introduce the distance-t chromatic number of a graph G of maximum degree D\, which is simply the chromatic number of G^t\, you can be interested in finding similar bounds\, and proving that they are tight. It is straight-forward that D^t is an upper bound for the distance-t chromatic number\, but determining how tight this bound is is far from being an easy problem. You may also wonder what happens to the bound of the distance-t chromatic number when you forbid some fixed lengths of cycles in your graph. The goal of my talk will be to give some answers to these natural questions. \n
URL:http://www.loria.fr/event/malotec-seminar/
LOCATION:B013
CATEGORIES:Séminaires
END:VEVENT
END:VCALENDAR