Kernelization Upper Bounds for Parameterized Graph Coloring Problems
Summary
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.