Kernelization Upper Bounds for Parameterized Graph Coloring Problems

Abstract

This thesis studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances, fol- lowing up on a paper by Jansen and Kratsch (FCT, 2011). In their paper they study how well polynomial-time data reductions can provably shrink instances of coloring problems, in terms of the chosen parameter. In this thesis we do the same except we use different parameters on slightly harder coloring problems. The paper by Jansen and Kratsch shows some interesting results about coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable, for example parame- terizing by the number k of vertex-deletions needed to make the graph chordal. In this thesis we obtain results on parameterizations of Chromatic Number. Every parameterization in this thesis is either by the number k of edge-deletions, edge-additions or edge-modifications (edge-deletions and edge-additions) needed to transform the input graph into a graph which is a member of a well known graph class, e.g. a forest. We obtain various upper and lower bounds for kernels of such parameterizations of Chromatic Number.