# Edge coloring strategy

I found the best edge coloring for the next two graphs.

But is there some strategy for it?

• Edge coloring is NP-Hard. The greedy algorithm is usually a good place to start. I am not familiar with any approximation algorithms off the top of my head, but that is also another good avenue to pursue. – ml0105 Dec 25 '17 at 20:54
• @ml0105 What do you mean with edge coloring is an NP-hard problem? Is Vertex coloring also NP-hard? – WinstonCherf Dec 26 '17 at 14:50
• Yes. Unless P=NP, I wouldn’t expect an easy solution to exist in general. – ml0105 Dec 26 '17 at 15:49

The main observation is that the edge-chromatic number will be at least the maximum degree, i.e., $\chi'(G) \geq \Delta(G)$, simply because each edge incident with a maximum-degree vertex must have different colors. In fact, Vizing's Theorem goes further and says $$\chi'(G) \in \{\Delta(G),\Delta(G)+1\}.$$
The first graph achieves $\chi'(G)=\Delta(G)$ (meaning it's class one), as you demonstrate. There's theoretical results which imply this, e.g., the Wikipedia page for Vizing's Theorem states "Vizing (1965) showed that a planar graph is of class one if its maximum degree is at least eight."
• In the given examples, the most difficult task is proving $\chi'(G) \neq \Delta(G)$ in the Petersen graph, since it requires effort to check it can't be $3$-edge-colored.
• A greedy-like algorithm would likely work in practice to give a $\chi'(G)$-edge coloring; generally, when there's one coloring, there's zillions of others.