ASU Electronic Theses and Dissertations
This collection includes most of the ASU Theses and Dissertations from 2011 to present. ASU Theses and Dissertations are available in downloadable PDF format; however, a small percentage of items are under embargo. Information about the dissertations/theses includes degree information, committee members, an abstract, supporting data or media.
In addition to the electronic theses found in the ASU Digital Repository, ASU Theses and Dissertations can be found in the ASU Library Catalog.
Dissertations and Theses granted by Arizona State University are archived and made available through a joint effort of the ASU Graduate College and the ASU Libraries. For more information or questions about this collection contact or visit the Digital Repository ETD Library Guide or contact the ASU Graduate College at gradformat@asu.edu.
Filtering by
- Creators: Czygrinow, Andrzej
$V$ to subsets of the natural numbers. An $L$-\emph{coloring} is a function $f$
with domain $V$ such that $f(v)\in L(v)$ for all vertices $v\in V$ and $f(x)\ne f(y)$
whenever $xy\in E$. If $|L(v)|=t$ for all $v\in V$ then $L$ is a $t$-\emph{list
assignment}. The graph $G$ is $t$-choosable if for every $t$-list assignment $L$
there is an $L$-coloring. The least $t$ such that $G$ is $t$-choosable is called
the list chromatic number of $G$, and is denoted by $\ch(G)$. The complete multipartite
graph with $k$ parts, each of size $s$ is denoted by $K_{s*k}$. Erd\H{o}s et al.
suggested the problem of determining $\ensuremath{\ch(K_{s*k})}$, and showed that
$\ch(K_{2*k})=k$. Alon gave bounds of the form $\Theta(k\log s)$. Kierstead proved
the exact bound $\ch(K_{3*k})=\lceil\frac{4k-1}{3}\rceil$. Here it is proved that
$\ch(K_{4*k})=\lceil\frac{3k-1}{2}\rceil$.
An online version of the list coloring problem was introduced independently by Schauz
and Zhu. It can be formulated as a game between two players, Alice and Bob. Alice
designs lists of colors for all vertices, but does not tell Bob, and is allowed to
change her mind about unrevealed colors as the game progresses. On her $i$-th turn
Alice reveals all vertices with $i$ in their list. On his $i$-th turn Bob decides,
irrevocably, which (independent set) of these vertices to color with $i$. For a
function $l$ from $V$ to the natural numbers, Bob wins the $l$-\emph{game} if
eventually he colors every vertex $v$ before $v$ has had $l(v)+1$ colors of its
list revealed by Alice; otherwise Alice wins. The graph $G$ is $l$-\emph{online
choosable} or \emph{$l$-paintable} if Bob has a strategy to win the $l$-game. If
$l(v)=t$ for all $v\in V$ and $G$ is $l$-paintable, then $G$ is t-paintable.
The \emph{online list chromatic number }of $G$ is the least $t$ such that $G$
is $t$-paintable, and is denoted by $\ensuremath{\ch^{\mathrm{OL}}(G)}$. Evidently,
$\ch^{\mathrm{OL}}(G)\geq\ch(G)$. Zhu conjectured that the gap $\ch^{\mathrm{OL}}(G)-\ch(G)$
can be arbitrarily large. However there are only a few known examples with this gap
equal to one, and none with larger gap. This conjecture is explored in this thesis.
One of the obstacles is that there are not many graphs whose exact list coloring
number is known. This is one of the motivations for establishing new cases of Erd\H{o}s'
problem. Here new examples of graphs with gap one are found, and related technical
results are developed as tools for attacking Zhu's conjecture.
The square $G^{2}$ of a graph $G$ is formed by adding edges between all vertices
at distance $2$. It was conjectured that every graph $G$ satisfies $\chi(G^{2})=\ch(G^{2})$.
This was recently disproved for specially constructed graphs. Here it is shown that
a graph arising naturally in the theory of cellular networks is also a counterexample.
number of colors needed to color $V(G)$ such that no adjacent vertices
receive the same color. The coloring number $\col(G)$ of a graph
$G$ is the minimum number $k$ such that there exists a linear ordering
of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.
It is well known that the coloring number is an upper bound for the
chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is
a generalization of the coloring number, and it was first introduced
by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$
is the minimum integer $k$ such that for some linear ordering $L$
of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller
vertices $u$ (with respect to $L$) with a path of length at most
$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.
The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$
is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$
if and only if the distance between $x$ and $y$ in $G$ is $3$.
This dissertation improves the best known upper bound of the
chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$
of planar graphs $G$, which is $105$, to $95$. It also improves
the best known lower bound, which is $7$, to $9$.
A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number.