A lecture on Some Generalized Coloring Problems
by Tınaz Ekim
(NoNA Spring School on Algorithms,
Istanbul, 12-15 March, 2009)
Abstract
We study some generalized vertex coloring problems, namely
Cocoloring, Split-coloring and (p,k)-coloring problems, where
we use not only stable sets but also cliques to partition the
vertex set of the given graph. Their computational complexity
is discussed in restricted classes of graphs such as cacti,
cographs, chordal graphs, line graphs and permutation graphs.
An application in permutation graphs is presented. We conclude
with some current research topics on Split-coloring and
Cocoloring problems.