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 |
---|---|
Dónde | Salón "Graciela Salicrup" |
Agregar evento al calendario |
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$.