Data Reduction for Graph Coloring Problems

B.M.P. Jansen, S. Kratsch

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    This paper studies the kernelization complexity of graph coloring problems, with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring problems, in terms of the chosen parameter. It is well known that deciding 3-colorability is already NP-complete, hence parameterizing by the requested number of colors is not fruitful. Instead, we pick up on a research thread initiated by Cai (DAM, 2003) who studied coloring problems parameterized by the modification distance of the input graph to a graph class on which coloring is polynomial-time solvable; for example parameterizing by the number k of vertex-deletions needed to make the graph chordal. We obtain various upper and lower bounds for kernels of such parameterizations of q-Coloring, complementing Cai's study of the time complexity with respect to these parameters.
    Original languageEnglish
    Title of host publicationProceedings 18th International Symposium on Fundamentals of Computation Theory, FCT 2011
    EditorsO. Owe, M. Steffen, J. A. Telle
    Number of pages12
    Publication statusPublished - 22 Aug 2011


    Dive into the research topics of 'Data Reduction for Graph Coloring Problems'. Together they form a unique fingerprint.

    Cite this