Ponente: Andre Raspaud (Université Bordeaux I)
05/11/2013
de 12:00 a 13:00
Dónde Salón "Graciela Salicrup"
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$.
Temas: