Usted está aquí: Strong chromatic index of planar graphs with large girth

# Strong chromatic index of planar graphs with large girth

Andre Raspaud (Université Bordeaux I) - martes 5 de noviembre, 12 horas
Ponente: Andre Raspaud (Université Bordeaux I)
Cuándo 05/11/2013 de 12:00 a 13:00 Salón "Graciela Salicrup" vCal iCal

Abstract:

A strong $k$-edge-coloring of a graph $G$ is a mapping from $E(G)$ to $\{1,2,\ldots,k\}$ such that every two adjacent edges or two edges adjacent to a same edge receive two distinct colors. In other words, the graph induced by each color class is an induced matching. This can also be seen as a vertex 2-distance coloring of the line graph of $G$.

Let $\Delta\ge 4$ be an integer. In this talk, we will give the sketch of the proof  that every planar graph with maximum degree $\Delta$ and girth at least $10\Delta+46$ is strong $(2\Delta -1)$-edge-colorable, that is best possible (in terms of number of colors) as soon as $G$ contains two adjacent vertices of degree $\Delta$.