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:

• Find a polynomial time algorithm that optimally colors interval graphs or prove that the problem is NP-hard.
• Same question for proper interval graphs (also known as indifference graphs).
• Same question for chordal graphs.

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:

• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; Ortiz, C.; Decompositions for the edge colouring of reduced indifference graphs. Theoretical Computer Science, 297(1-3) pp. 145-155, March 2003. In this paper we prove that indifference graphs with no twin vertices cannot be neighborhood-overfull and are Class 1. DOI reference (PDF available)
• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; Local conditions for edge-coloring. Journal of Combinatorial Mathematics and Combinatorial Computing, 32, pp. 79-91, 2000. In this paper we prove that neighborhood-overfullness is equivalent to subgraph-overfullness in indifference graphs, and other results. A working draft follows. Download pdf
• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; Total chromatic number and chromatic index of dually chordal graphs. Information Processing Letters, 70 (3), pp. 147-152, 1999. In this paper we prove that the total-colour conjecture holds for dually chordal graphs. DOI reference. A working draft follows. Download pdf
• Meidanis, J.; Edge Coloring of Cycle Powers is Easy. In this paper we prove that a cycle power is in Class 1 if and only if it has an even number of vertices, thus generalizing known results for cycles and complete graphs. Unpublished manuscript, 1998. A working draft follows. Download pdf
• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; On edge-colouring indifference graphs. Theoretical Computer Science 181, pp. 91-106, 1997. Here we solve the problem for indifference graphs with at most three maximal cliques. We believe the techniques can be applied to the full class. DOI reference (PDF available).
• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; A greedy method for edge-colouring odd maximum degree doubly chordal graphs. Congressus Numerantium, 111, pp.170-176, 1995. A draft follows. Download pdf
• Figueiredo, C. M. H.; Meidanis, J.; Mello, C. P.; A linear-time algorithm for proper interval graph recognition. Information Processing Letters, 56 (3), pp. 179-184, 1995. Not about edge coloring, but this was the start. DOI reference. A working draft follows. Download pdf