Files in this item



application/pdfMAHONEY-DISSERTATION-2015.pdf (778kB)
(no description provided)PDF


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
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):graph coloring
list coloring
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
Rights Information:Copyright 2015 Thomas R. Mahoney
Date Available in IDEALS:2015-09-29
Date Deposited:August 201

This item appears in the following Collection(s)

Item Statistics