## Files in this item

FilesDescriptionFormat

application/pdf

MAHONEY-DISSERTATION-2015.pdf (778kB)
(no description provided)PDF

## Description

 Title: Online choosability of graphs Author(s): Mahoney, Thomas R Director of Research: West, Douglas B. Doctoral Committee Chair(s): Kostochka, Alexandr V. Doctoral Committee Member(s): Molla, Theodore; Schupp, Paul E. Department / Program: Mathematics Discipline: Mathematics Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): graph coloring list coloring choosability paintability online list coloring online choosability Abstract: 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 Issue Date: 2015-07-09 Type: Thesis URI: http://hdl.handle.net/2142/88001 Rights Information: Copyright 2015 Thomas R. Mahoney Date Available in IDEALS: 2015-09-29 Date Deposited: August 201
﻿