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.