|
Evènement pour le groupe GT Graphes et Applications
Date | 2014-03-07 14:00-15:00 |
Titre | Planar 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? |
Lieu | Salle 178 |
Orateur | André Raspaud |
Aucun document lié à cet événement. RetourRetour à l'index
| |