Distance-two colorings of graphs

Abstract

Dans cette thèse, on s’intéresse en particulier à la coloration du carré des graphes planaires (deux sommets à distance au plus deux ont des couleurs distinctes) et à la coloration cyclique des graphes planaires (deux sommets incidents à la même face ont des couleurs distinctes). On montre un résultat général qui implique que deux conjectures importantes sur ces colorations (Wegner 1977 et Borodin 1984) sont vraies asymptotiquement. On s’intéresse également à d’autres colorations à distance deux, qui ont des liens (plus ou moins vagues) avec l’allocation de fréquences dans les réseaux radios, la théorie des jeux, la sociologie et l’écologie.