
Evènement pour le groupe GT Graphes et Applications
Date  20150206 14:0015:00 
Titre  Strong edgecoloring of (3, Delta)bipartite graphs 
Résumé  An edgecoloring 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 edgecoloring of G. A longstanding 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 upperbounded 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. 
Lieu  Salle 178 
Orateur  Julien Bensmail 
Aucun document lié à cet événement. RetourRetour à l'index
 