Max-coloring and online coloring

non-negative weights on the vertices. We define the weight of any proper
vertex coloring of G as follows: The cost of a color class is the
maximum weight of any vertex in this color class, and the cost of a
coloring is the sum of the weights of the color classes. The objective
is to compute a minimum weight coloring of G. The problem arises in
batch scheduling of conflicting jobs and buffer minimization.
In the online coloring problem, the graph is not known to the algorithm
at the start, and vertices are presented one at a time to the algorithm.
When a vertex is presented, the edges to previously presented vertices
is also revealed. The algorithm irrecoverably assigns a color to the
vertex before the next vertex is revealed. The objective is to assign
colors to minimize the number of colors used.
In this talk I will focus on approximation algorithms for the
max-coloring problem on various classes of graphs, and on the analysis
of the first-fit algorithm for interval graphs.