Evènement pour le groupe GT Graphes et Applications

Date 2014-03-07  14:00-15:00
TitrePlanar graphs with minimum cycle length at least 5 are (3,5)-colorable  
RésuméA graph is (d_1,...., d_r)-colorable if its vertex set can be partitioned into r sets V_1,......, V_r where the maximum degree of the graph induced by V_i is at most d_i for each i in {1,... r}. Let G_g denote the class of planar graphs with minimum cycle length at least g. We focus on graphs in G_5 since for any d_1 and d_2, Montassier and Ochem constructed graphs in G_4 that are not (d_1, d_2)-colorable. It is known that graphs in G_5 are (2, 6)-colorable and (4, 4)-colorable, but not (3, 1)-colorable. We prove that graphs in G_5 are (3, 5)-colorable, leaving two interesting questions open: (1) are graphs in G_5 also (3, d_2)-colorable for some d_2 in {2, 3, 4}? (2) are graphs in G_5 indeed (d_1, d_2)-colorable for all d_1+d_2=8 where d_2>= d_1 >=1?  
LieuSalle 178 
OrateurAndré Raspaud 

Aucun document lié à cet événement.

Retour à l'index