# graph theory, relation between chromatic index and maximum matching

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.

-

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.

-
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