Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorNederlof, J.
dc.contributor.authorMeijer, Lucas
dc.date.accessioned2022-11-24T01:01:08Z
dc.date.available2022-11-24T01:01:08Z
dc.date.issued2022
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/43232
dc.description.abstractWe 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.
dc.description.sponsorshipUtrecht University
dc.language.isoEN
dc.subjectWe improved upon previously the best algorithm for 3-Coloring, which also improved 4-Coloring. Minor improvements were also found for vertex cover coloring, and new lower bounds on the maximum number of maximal induced k-colorable subgraphs in a graph.
dc.titleGraph Coloring
dc.type.contentMaster Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsGraph Theory; Graph Coloring; 3-Coloring; 4-Coloring; Vertex Cover Coloring; Maximal Induced k-Colorable Subgraphs
dc.subject.courseuuComputing Science
dc.thesis.id12231


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record