GRAPH Course

Edge coloring

Go back

The idea is the same as for the vertex coloring. We will use "chromatic index" (indice chromatique) instead of "chromatic number".

Line graph

The line graph $L(G)$ of a graph $G$ is made using $G$ edges. This is convenient because the chromatic number of $L(G)$, is the chromatic index of $G$. You can create the line graph from $G$ following this

  • a vertex of $L$ is an edge of $G$
  • two vertices of $L$ are linked if they are incident to the same vertex in $G$.