Lanterna Rally

Author: Peter Bradshaw

Publisher:

Published: 2022

Total Pages: 0

ISBN-13:

A graph coloring is an assignment of a label, usually called a color, to each vertex of a graph. In nearly all applications of graph coloring, the colors on a graph's vertices must avoid certain forbidden local configurations. In this thesis, we will consider several problems in which we aim to color the vertices of a graph while obeying more complex local restrictions presented to us by an adversary. The first problem that we will consider is the list coloring problem, in which we seek a proper coloring of a graph in which every vertex receives a color from a prescribed list given to that vertex by an adversary. We will consider this problem specifically for bipartite graphs, and we will take a modest step toward a conjecture of Alon and Krivelevich on the number of colors needed in the list at each vertex of a bipartite graph in order to guarantee the existence of a proper list coloring. The second problem that we will consider is single-conflict coloring, in which we seek a graph coloring that avoids a forbidden color pair prescribed by an adversary at each edge. We will prove an upper bound on the number of colors needed for a single-conflict coloring in a graph of bounded degeneracy. We will also consider a special case of this problem called the cooperative coloring problem, and we will find new results on cooperative colorings of forests. The third problem that we will consider is the hat guessing game, which is a graph coloring problem in which each coloring of the neighborhood of a vertex v determines a single forbidden color at v, and we aim to color our graph so that no vertex receives the color forbidden by the coloring of its neighborhood. We will prove that the number of colors needed for such a coloring in an outerplanar graph is bounded, and we will extend our method to a large subclass of planar graphs. Finally, we will consider the graph coloring game, a game in which two players take turns properly coloring the vertices of a graph, with one player attempting to complete a proper coloring, and the other player attempting to prevent a proper coloring. We will show that if a graph G has a proper coloring in which the game coloring number of each bicolored subgraph is bounded, then the game chromatic number of G is bounded. As a corollary, we will obtain upper bounds for the game chromatic numbers of certain graph products and answer a question of X. Zhu.