Accéder aux actualités Evènements des groupes Liste des groupes publics
Evènement pour le groupe GT Graphes et Applications

 Date 2011-04-01  14:00-15:00 Titre Décomposition de graphes Résumé A graph G is called improperly (d1, ... dk )-colorable, or just (d1, ... dk )-colorable, if the vertex set of G can be partitioned into subsets V1, ... Vk such that the graph G[Vi] induced by the vertices of Vi has maximum degree at most di for all 1 ≤ i ≤ k. This notion generalizes those of proper k-coloring (when d1 = ... = dk = 0) and d-improper k-coloring (when d1 = ... = dk = d ≥ 1). Proper and d-improper colorings have been widely studied. As shown by Appel and Haken, every planar graph is 4-colorable, i.e. (0, 0, 0, 0)-colorable. Eaton and Hull and independently Skrekovski proved that every planar graph is 2-improperly 3-colorable (in fact, 2-improper choosable), i.e. (2,2,2)-colorable. This latter result was extended by Havet and Sereni to not necessarily planar sparse graphs as follows: Theorem. For every k ≥ 0, every graph G with mad(G) < (4k+4)/(k+2) is k-improperly 2-colorable (in fact k-improperly 2-choosable), i.e. (k,k)-colorable. We recall that mad(G) = {max(2|E(H)|/|V(H)|),H ⊆ G}, is the maximum average degree of a graph G. In this talk we will present obtained results concerning the (k, j)-colorability for some values of k and j (k = j) for graphs with a given maximum average degree. Lieu Salle 178 Orateur André Raspaud

1 document lié:
résumé

Retour
Retour à l'index