1
$\begingroup$

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.

1 Answers 1

2

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.

  • 0
    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.2011-12-10