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

        Graph Coloring

        Thumbnail
        View/Open
        Graph Coloring Thesis - Lucas Meijer (6141978).pdf (1.290Mb)
        Publication date
        2022
        Author
        Meijer, Lucas
        Metadata
        Show full item record
        Summary
        We discuss many coloring problems. Most notably, we devise a modified algorithm for 3-coloring that has a worst-case time bound of O(1.3236^n). We obtain this by adapting Beigel and Eppstein's time O(1.3289^n) algorithm. They found a structure in the graph that could be colored relatively easily called a maximal bushy forest, which we modify to limit the number of relatively difficult-to-color vertices by dividing the vertices in the graph using their relation to the bushy forest. Furthermore, we take a look at how a small vertex cover can be used to quickly find a k-coloring of a graph. Finally, we contribute new lower bounds for maximal induced k-colorable subgraphs, discuss the properties of these graphs and the upper bound on the number of maximal induced k-colorable subgraphs on graphs with these properties.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43232
        Collections
        • Theses

        Related items

        Showing items related by title, author, creator and subject.

        • Seeing Color? Where? Current Standing in Projector and Associator Grapheme-Color Synesthesia Research. 

          Leeuwen, J. van (2015)
          Synesthesia is a neurological condition where a perceptual experience of a stimulus triggers a new perceptual experience, which is not caused in non-synesthetes. For instance, in grapheme-color synesthesia, a black grapheme ...
        • Color Remapping: Perceptual evaluation of colorized nighttime imagery 

          Jong, M.J. de (2015)
          In this study an evaluation of different night imagery was conducted. Adding ecologically valid colors to night imagery is thought to result in better scene recognition and object detection. Two experiments were performed ...
        • Transgender people of color: double injustice? 

          Umuhire, Sandrine (2022)
          Introduction: Despite the number of laws that should minimize the disadvantages of transgender people in America, discrimination is still a problem among this group. Several studies show that transgender people in America ...
        Utrecht university logo