View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Kernelization Upper Bounds for Parameterized Graph Coloring Problems

        Thumbnail
        View/Open
        PaperKernelization.pdf (371.4Kb)
        Publication date
        2013
        Author
        Weijer, P. de
        Metadata
        Show full item record
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/14916
        Collections
        • Theses
        Utrecht university logo