Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

consider the following algorithm to find a minimum edge coloring in a graph G=(V,E)

let k = 0
while E has edges:
 k = k+1
 Let M be a maximum matching in G=(V,E)
 For every e in M, mark e with color k
 E = E - M

Could you find a proof (counter example?) that for some graph G it does not find G's chromatic index? It has to exists otherwise edge coloring would be in P since there is a polynomial time algorithm to find a maximum matching.

share|cite|improve this question
up vote 2 down vote accepted

This algorithm can fail if you start with the five vertex graph built from a square with an additional central point connected to each vertex of the square (such graphs are sometimes called wheels, although this particular wheel won't work so well on a wheelbarrow). If the first matching avoids the central point, the algorithm will return at best an edge five coloring, whereas the graph itself is edge four colorable.

share|cite|improve this answer
I suppose a simpler example would be a path on five vertices (four edges). If the first matching picks the outermost pair of edges, the algorithm will guess chromatic index three instead of the correct answer of two. – user83827 Dec 10 '11 at 14:44
thats a good example. therefore there's no limit on how bad this approximation is compared to the chromatic index? for example a center vertex joining togheter n P5's could be n colors apart from the optimum coloring. – Ed Fox Dec 10 '11 at 18:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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