dc.rights.license | CC-BY-NC-ND | |
dc.contributor.advisor | Nederlof, J. | |
dc.contributor.author | Meijer, Lucas | |
dc.date.accessioned | 2022-11-24T01:01:08Z | |
dc.date.available | 2022-11-24T01:01:08Z | |
dc.date.issued | 2022 | |
dc.identifier.uri | https://studenttheses.uu.nl/handle/20.500.12932/43232 | |
dc.description.abstract | 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. | |
dc.description.sponsorship | Utrecht University | |
dc.language.iso | EN | |
dc.subject | We 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.title | Graph Coloring | |
dc.type.content | Master Thesis | |
dc.rights.accessrights | Open Access | |
dc.subject.keywords | Graph Theory; Graph Coloring; 3-Coloring; 4-Coloring; Vertex Cover Coloring; Maximal Induced k-Colorable Subgraphs | |
dc.subject.courseuu | Computing Science | |
dc.thesis.id | 12231 | |