Graph Coloring
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.
Collections
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 ... -
Studying Digital Music: Coloring, Sculpting and Playing in Sound
Harder, Hannah (2021)This thesis explores ways in media and performance studies to analyze digital music, particularly hip-hop music, through its production practice. Although the formal elements of popular music such as hip-hop include ...