Files in this item
Files  Description  Format 

application/pdf MAHONEYDISSERTATION2015.pdf (778kB)  (no description provided) 
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 UrbanaChampaign 
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:  20150709 
Type:  Thesis 
URI:  http://hdl.handle.net/2142/88001 
Rights Information:  Copyright 2015 Thomas R. Mahoney 
Date Available in IDEALS:  20150929 
Date Deposited:  August 201 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois