Journées de l'optimisation 2007 Optimizations days

Given a graph G=(V,E) with strictly positive edge weights w(i,j) on each edge {i,j} in E, the bandwidth coloring problem is to determine a minimum k such that there is a function c that assigns an integer value c(v) in {1,…,k} to each vertex v of V with the property that |c(i)-c(v)| is at least equal to w(i,j) for every edge {i,j} in E. Given a graph G=(V,E) with strictly positive node weights w(i) for each vertex i in V, the interval coloring problem is to determine a minimum k such that one can assign an interval S(v) of consecutive integers in {1,…,k} to each vertex v of V with the property that S(i) and S(j) do not share any common integer for every edge {i,j} in E. Let W be the largest weight on a vertex of G and let N be the number of different weights in G, we prove that the interval coloring problem can be reduced to the solution of max{log W, N}+1 bandwidth coloring problems.

An edge coloring of a graph G is a function that assigns a color c(e) to each edge e such that c(e) is different from c(e') whenever e and e' have a common endpoint. Denoting S(v,G,c) the set of colors assigned to the edges incident to a vertex v, and D(v,G,c) the minimum number of integers which must be added to S(v,G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum of the values D(v,G,c) over all vertices of G, and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.

We consider the bandwidth coloring problem, a generalization of the well-known graph coloring problem. For the latter problem, a well-known theorem, discovered independently by Gallai, Roy and Vitaver, states that the chromatic number of a graph is at least equal to the number of vertices in the longest path in any directed graph derived by orienting all edges in the graph. We generalize this result to the bandwidth coloring problem. Our proof is based on a series of equivalent mathematical programming models, and uses linear programming duality. These results not only generalize Gallai-Roy-Vitaver theorem (providing an alternative proof for the special case of the graph coloring problem), but they also hint at several mathematical programming formulations that can motivate the development of various solution algorithms for the bandwidth coloring problem.