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.
-
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 ... -
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 ... -
Zeroed out: Reproductive Justice for Women of Color held in immigrant detention in the U.S. The 2020 Irwin County Detention Center case
Levy Mora, ALMA (2021)The U.S. has a colonial and imperialist history of reproductive oppression towards women’s bodies, sexuality, labor, reproduction, and parenting. Although feminist groups in the U.S. have advocated for decades to obtain ...