Evènement pour le groupe GT Graphes et Applications

Date 2015-02-06  14:00-15:00
TitreStrong edge-coloring of (3, Delta)-bipartite graphs 
RésuméAn edge-coloring of a graph G is strong if its every color class is an induced matching. The strong chromatic index of G, denoted chi'_s(G), is the least number of colors in a strong edge-coloring of G. A long-standing conjecture of Erdos and Nesetril (1989) states that the right upper bound on the strong chromatic index should be roughly 1.25Delta^2, which would be tight as confirmed by a particular family of graphs with a lot of small cycles (C_4's and C_5's). Excluding small cycles i.e. with length at most 5) in a graph is expected to make its strong chromatic index decrease. This made Faudree, Gyarfas, Schelp and Tuza (1990) conjecture that the strong chromatic index of bipartite graphs (which have no C_3's and C_5's) should be upper-bounded by Delta^2. In the continuity of previous results of Steger and Yu (1993) and Nakprasit (2008), we verify this conjecture for bipartite graphs whose one part is of maximum degree at most 3. This is a joint work with A. Lagoutte and P. Valicov.  
LieuSalle 178 
OrateurJulien Bensmail 

Aucun document lié à cet événement.

Retour à l'index