
Evènement pour le groupe GT Graphes et Applications
Date  20110401 14:0015: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 kcoloring (when d1 = ... = dk = 0) and dimproper kcoloring (when d1 = ... = dk = d ≥ 1).
Proper and dimproper colorings have been widely studied. As shown by Appel and Haken, every planar graph is 4colorable, i.e. (0, 0, 0, 0)colorable. Eaton and Hull and independently Skrekovski proved that every planar graph is 2improperly 3colorable (in fact, 2improper 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 kimproperly 2colorable (in fact kimproperly 2choosable), i.e. (k,k)colorable.
We recall that mad(G) = {max(2E(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é:  