How do I color edges in a graph?

I actually want to ask you specifically about one method that I've heard about - to find a dual (?) graph and color its vertices. What is the dual graph here? Is it really the dual graph, or maybe something different? If so, what is this?

The graph I'm talking about has G* sign.


One method of finding an edge colouring of a graph is to find a vertex colouring of it's line graph. The line graph is formed by placing a vertex for every edge in the original graph, and connecting them with edges if the edges of the original graph share a vertex.

By finding a vertex colouring of the line graph we obtain a colour for each edge, and if two edges of the original graph share an endpoint they will be connected in the line graph and so have different colours in our colouring. From this we can see that a vertex colouring of the line graph gives an edge colouring of our initial graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.