On-line algorithms and on-line coloring

May 23, 2016

Nicolas Gastineau (Univ. Bourgogne Franche-Comté)

In graph theory, an on-line algorithm considers a graph and an order on the vertices of this graph, takes a decision for each vertex following the order and only knowing information about the previous vertices. In this talk, we focus on the on-line coloring problem in order to illustrate the behavior of such algorithms. Afterwards, we present the Grundy coloring which is the best known on-line coloring algorithm. We present some results about the complexity of decision problems for on-line and Grundy coloring. Finally, we present several theorems about the maximal number of color the Grundy coloring can give for different classes of graphs.