Edge Coloring

Edge coloring a graph means assigning colors to edges so that adjacent edges get different colors, using the minimum number of colors in the process. This is a difficult problem. Although it is known that every graph G can be edge colored with at most Delta(G)+1 colors, and that at least Delta(G) colors are always necessary, it is NP-hard to decide between these two consecutive integers. (Delta(G) is the maximum degree of G.)

However, the problem becomes polynomial in certain graph classes. My main objective is to study edge coloring in interval graphs and related classes. I do not have any particular application in mind, just started in these classes because I knew a whole lot about them due to my studies of DNA fragment assembly problems.

My colleagues Celia Picinin de Mello, from UNICAMP, and Celina Miraglia Herrera de Figueiredo, from the Federal University of Rio de Janeiro, are my most frequent co-authors in this topic.

Here are some open questions of interest:

The questions have been solved for graphs in the above classes and odd maximum degree. In this case they are all Class 1, that is, can be edge colored with Delta(G) colors.

Here are some of our papers on the subject:

Last modified: Fri Oct 7 12:17:16 BRST 2005 by JM