1 Presentation

• 
  10:30 AM - 12:10 PM

  Variations and Extensions of the Standard Vertex Coloring Problem

  • Alain Hertz, presenter, Polytechnique Montréal and GERAD

  Given a graph G = (V;E) with vertex set V and edge set E, and given an integer k, a k-coloring of G is a function c : V -> {1, ... k} that assigns a color c(v) to every vertex v so that no edge has both endpoints with the same color. The vertex coloring problem is to determine the smallest integer k, called chromatic number, for which G admits a k-coloring. Variations and extensions of this famous combinatorial optimization problem have been developed to deal with increasingly complex scheduling problems. We present some of them and illustrate them in specific applications. We first consider the selective graph coloring problem which can be defined as follows. Let V = {V1, ..., Vp} be a partition of the vertex set V. We define a selection as a subset of vertices V' (in V) such that the intersection of V' and Vi is exactly of size 1 for all i. A selective k-coloring of G with respect to the partition V is defined by (V',c), where V' is a selection and c is a k-coloring of the subgraph induced by the selection V'. The smallest integer k for which G admits a selective k-coloring with respect to V is called the selective chromatic number.
  The standard vertex coloring problem is often used to solve scheduling problems involving incompatibility constraints. For more general scheduling problems with precedence constraints, the second considered generalisation, called mixed graph coloring problem, is a more appropriate model. The minimum number of colors needed to color the vertices of a mixed graph is called the mixed chromatic number.
  In practical applications, it may happen that the graph to be colored is not known from the beginning. The input graph is then only partially available because some relevant input arrives only in the future. This is the case, for example, in dynamic storage allocation, or when assigning channels (colors) to users (vertices) in a telecommunication network. In such situations, the vertices arrive one by one together with
  the edges linking them to previously revealed vertices. An online algorithm must color the vertices as they arrive, and no color can be changed later. The online chromatic number of G is then defined as the smallest number k such that there exists a online algorithm which is able to color G using k colors for any incoming order of the vertices.