Evènement pour le groupe GT Graphes et Applications

Date 2011-04-01  14:00-15:00
TitreDé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. 
LieuSalle 178 
OrateurAndré Raspaud 

1 document lié: