Group for Research in Decision Analysis

A colourful look on graph theory

Alain Hertz Professor, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Canada

Given a graph \(G\) with a vertex set \(V\) and an edge set \(E\), we consider problems consisting in coloring the vertices and/or the vertices of G. When the vertices are colored, we impose the constraint that the endpoints of each edge should have a different color, while in edge coloring problems, no two adjacent edges can have the same color.

Graph coloring is a basic model for numerous and various applications where a partition of a conflicting set of objects has to be found. Each bloc of the partition can only contain non conflicting objects. When the objects are represented by vertices, each conflict between two objects is associated with an edge between the two corresponding vertices, while when the objects are represented by edges, it is imposed that two edges corresponding to two conflicting objects should have a common endpoint.

Graph coloring is a natural model for scheduling problems where the tasks to be planed are the objects and each bloc of the partition corresponds to a period of the schedule. There is a conflict between two objects if they cannot be scheduled at the same time. Other applications of graph coloring are, for example, frequency assignment problems in telecommunication, inventory problems with dangerous items, or train re-composition in railway stations. Some of these applications require an extension of the basic graph coloring models. One can for example be interested in « weighted » « cyclic » or « list » colorings. The aim of this talk is to give an overview of the basic graph coloring models and their most famous extensions.