Coloration circulaire par listes
Frédéric Havet
Projet Mascotte
Abstract:
Soit G = (V , E ) un graphe et p et q deux entiers avec p plus grand
que q. Une (p,q)-coloration de G est une fonction c de V dans
{0,...,p-1} telle que, pour toute arête uv , q ≤ |c(u)-c(v
)| ≤ p-q. Le nombre chromatique circulaire de G est
chic (G) = inf{p/q : G admet une (p,q)-coloration}
La coloration circulaire peut-être vu comme un
raffinement de la coloration: en particulier,
chi(G) - 1 < chic (G) ≤ chi(G) pour tout graphe G.
(chi(G) est le nombre chromatique de G).
Récemment, Zhu a introduit la notion de coloration circulaire
par listes qui généralise la
coloration circulaire de la même manière que la
coloration par listes généralise la coloration classique.
Après avoir gentiment
introduit cette notion, nous montrerons quelques résultats
sur la coloration circulaire par listes. En particulier, nous
montrerons que le maximum du nombre chromatique circulaire par listes
des graphes planaires est compris entre 6 et 8. Ceci contredit une
conjecture de Mohar qui disait que c'était entre 4 et 5.
Travail en commun avec R. Kang, T. Muller et J.-S. Sereni
Retour au séminaire