There is no mention of colo(u)r in the whole POD of Graph

Because then there is no need to write one's own add_edges etc. Graph does not have colouring methods for now, but pull-requests adding them (ideally with tests) are always welcome.

> but pull-requests adding them (ideally with tests) are always welcome.

Graph coloring is a vast field, IMHO this would need to be addressed in an extra module.

I was lucky to find a satisfying optimal solution, but only for the edge coloring of complete graphs (like requested by the OP)

This edge-case (sic ;) can hardly be included in your very general module.

And there is no easy generalization, according to WP is the general case of an optimal coloring known to be NP-hard.

Cheers Rolf
_{(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery}