Loading Events

« All Events

  • This event has passed.

MALOTEC Seminar

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.

Details

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

Venue

B013

Logo du CNRS

Logo d'Inria

Logo Université de Lorraine