Abstract: Vertex colorings of graphs is an active research area with
many practical applications in fields like operations research (e.g.,
scheduling) and computer science (e.g., register allocation), but also
many theoretical challenges and open problems.
We consider unique-maximum and conflict-free vertex colorings of graphs
which are stronger versions of traditional vertex coloring.
These two colorings have applications in:
* efficient solving of sparse linear systems of equations,
* scheduling parallel assembly of products,
* finding local optima in neighborhood structures,
* frequency assignment in cellular, wireless, and sensor networks.

A unique-maximum coloring of a graph G is an assignment of colors (i.e.,
positive integers) to the vertices of G such that in every simple path p of G
the maximum color that occurs in p, occurs exactly one time in p.
In a conflict-free coloring of G, in every simple path p of G, there must be
a color that occurs exactly one time in p (not necessarily the maximum one
in p). 

We present results on the computational complexity of the above colorings
and we investigate the relation between the two colorings. We introduce games
on graphs that are closely related to the above colorings and prove lower and
upper bounds on the optimal number of colors of a unique-maximum and
a conflict-free coloring for some families of graphs.

Time permitting, we will also mention some results on conflict-free colorings
with respect to neighborhoods of vertices in a graph.