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 ... -
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 ...