Loading Events

« All Events

  • This event has passed.


October 5, 2016 @ 3:00 pm - 4:00 pm

The first MALOTEC seminar of the season will take place on Wednesday, October 5th, from 3PM to 4PM in room B013.

François Pirot will give a presentation entitled “The bounds for the distance-t chromatic number, and the effect of removing cycles”.

Abstract : 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.

When 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.


October 5, 2016
3:00 pm - 4:00 pm
Event Category:



Logo du CNRS

Logo d'Inria

Logo Université de Lorraine