A lecture on Some Generalized Coloring Problems by Tınaz Ekim

(NoNA Spring School on Algorithms, Istanbul, 12-15 March, 2009)


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.