An edge is adjacent to at most $2\Delta (G) -1$ edges.

154 Views Asked by At

When I was looking at upper bounds for chromatic index $\chi '$ in a graph, i.e. the least number of colors needed to color the edge set, I saw that an upper bound is $2\Delta (G) -1$, where $\Delta (G)$ is the maximum degree in a graph $G$. This follows by noting that the chromatic index of $G$ is equal to the chromatic number $\chi$ (min.number of colors needed to color the vertex set of $G$) of the line graph of $G$.

The line graph ($L(G)$)of $G$ is the graph obtained by $G$, whose vertices are the edges of $G$ and two vertices are adjacent when they share and endpoint in $G$. Now we have $$\chi'(G)=\chi(L(G))\leq \Delta (G)+1 \leq 2\Delta (G)-1 $$ I do not know if I understood this upper bound very well: Let $e$ be an edge with endpoints $u$ and $v$. Since $d_G(u),d_G(v)\leq \Delta (G)$ then $d_{L(G)}(e) \leq 2\Delta (G)$ and then we add $-1$ since it is not adjacent to itself. Can someone let me know if this is correct?