MASCOTTE no longer exists => visit the new COATI project-team
 


Seminaire MASCOTTE
Coloration faciale

par Frédéric Havet


Date :18/03/08
Location :Fermat Jaune


Travail en collaboration avec D. Kral, J.-S. Sereni et R. Skrelovki.

Un graphe plan est l-facialement k-colorable si ses sommets peuvent etre colorés avec k couleurs de telle facon que deux sommets distincts reliés par une marche faciale (qui suit le bord d'une face) de longueur au plus l aient des couleurs différentes. Kral, Madaras et Skrekovski ont conjecturé que tous les graphes plans sont l-facialement (3l+1)-colorables et ont montré qu'ils étaient l-facialement (3,6l+2)-colorables. Nous montrons ici qu'ils sont l-facialement (3,5l+6)-colorables. La preuve utilise la méthode de déchargement et le théorème de Hall pour trouver des configurations réductibles.



Page des séminaires