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)\to\N$, we say that $G$ is $f$-choosable if $G$ is $L$-colorable for any list assignment $L$ such that $|L(v)|\ge f(v)$ for all $v\in 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(K_{k,r})\le k$ if and only if $r
PDF
download
878987797
028-85220240
