Exact algorithm for edge coloring
You can edge color faster than applying the fastest vertex coloring algorithm to the line graph: see http://arxiv.org/abs/1007.1161 for one such algorithm. What interests me is why can't we find something that is much faster...