AbstractsMathematics

We study several problems in graph coloring. In list coloring, each vertex v has a set L(v) of available colors and must be assigned a color from this set so that adjacent vertices receive distinct colors; such a coloring is an L-coloring, and we then say that G is L-colorable. Given a graph G and a function f:V(G) → N, we say that G is f-choosable if G is L-colorable for any list assignment L such that |L(v)| ≥  f(v) for all v∈ V(G). When f(v)=k for all v and G is f-choosable, we say that G is k-choosable. The least k such that G is k-choosable is the choice number, denoted ch(G). We focus on an online version of this problem, which is modeled by the Lister/Painter game. The game is played on a graph in which every vertex has a positive number of tokens. In each round, Lister marks a nonempty subset M of uncolored vertices, removing one token at each marked vertex. Painter responds by selecting a subset D of M that forms an independent set in G. A color distinct from those used on previous rounds is given to all vertices in D. Lister wins by marking a vertex that has no tokens, and Painter wins by coloring all vertices in G. When Painter has a winning strategy, we say that G is f-paintable. If f(v)=k for all v and G is f-paintable, then we say that G is k-paintable. The least k such that G is k-paintable is the paint number, denoted pa(G). In Chapter 2, we develop useful tools for studying the Lister/Painter game. We study the paintability of graph joins and of complete bipartite graphs. In particular, pa(Kk,r) ≤  k if and only if r