Files in this item
Files  Description  Format 

application/pdf LOEBDISSERTATION2017.pdf (648kB)  (no description provided) 
Description
Title:  Coloring and covering problems on graphs 
Author(s):  Loeb, Sarah Jane 
Director of Research:  West, Douglas B. 
Doctoral Committee Chair(s):  Kostochka, Alexandr 
Doctoral Committee Member(s):  Yong, Alexander; Molla, Theodore 
Department / Program:  Mathematics 
Discipline:  Mathematics 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Graph coloring
Graph covering 
Abstract:  The \emph{separation dimension} of a graph $G$, written $\pi(G)$, is the minimum number of linear orderings of $V(G)$ such that every two nonincident edges are ``separated'' in some ordering, meaning that both endpoints of one edge appear before both endpoints of the other. We introduce the \emph{fractional separation dimension} $\pi_f(G)$, which is the minimum of $a/b$ such that some $a$ linear orderings (repetition allowed) separate every two nonincident edges at least $b$ times. In contrast to separation dimension, we show fractional separation dimension is bounded: always $\pi_f(G)\le 3$, with equality if and only if $G$ contains $K_4$. There is no stronger bound even for bipartite graphs, since $\pi_f(K_{m,m})=\pi_f(K_{m+1,m})=\frac{3m}{m+1}$. We also compute $\pi_f(G)$ for cycles and some complete tripartite graphs. We show that $\pi_f(G)<\sqrt{2}$ when $G$ is a tree and present a sequence of trees on which the value tends to $4/3$. We conjecture that when $n=3m$ the $K_4$free $n$vertex graph maximizing $\pi_f(G)$ is $K_{m,m,m}$. We also consider analogous problems for circular orderings, where pairs of nonincident edges are separated unless their endpoints alternate. Let $\pi^\circ(G)$ be the number of circular orderings needed to separate all pairs, and let $\pi_f^\circ(G)$ be the fractional version. Among our results: (1) $\pi^\circ(G)=1$ if and only $G$ is outerplanar. (2) $\pi^\circ(G)\le2$ when $G$ is bipartite. (3) $\pi^\circ(K_n)\ge\log_2\log_3(n1)$. (4) $\pi_f^\circ(G)\le\frac{3}{2}$, with equality if and only if $K_4\subseteq G$. (5) $\pi_f^\circ(K_{m,m})=\frac{3m3}{2m1}$. A \emph{star $k$coloring} is a proper $k$coloring where the union of any two color classes induces a star forest. While every planar graph is 4colorable, not every planar graph is star 4colorable. One method to produce a star 4coloring is to partition the vertex set into a 2independent set and a forest; such a partition is called an \emph{\Ifp}. We use discharging to prove that every graph with maximum average degree less than $\frac{5}{2}$ has an \Ifp, which is sharp and improves the result of Bu, Cranston, Montassier, Raspaud, and Wang (2009). As a corollary, we gain that every planar graph with girth at least 10 has a star 4coloring. A proper vertex coloring of a graph $G$ is \emph{$r$dynamic} if for each $v\in V(G)$, at least $\min\{r,d(v)\}$ colors appear in $N_G(v)$. We investigate $3$dynamic versions of coloring and list coloring. We prove that planar and toroidal graphs are 3dynamically 10choosable, and this bound is sharp for toroidal graphs. Given a proper total $k$coloring $c$ of a graph $G$, we define the \emph{sum value} of a vertex $v$ to be $c(v) + \sum_{uv \in E(G)} c(uv)$. The smallest integer $k$ such that $G$ has a proper total $k$coloring whose sum values form a proper coloring is the \emph{neighbor sum distinguishing total chromatic number} $\chi''_{\Sigma}(G)$. Pil{\'s}niak and Wo{\'z}niak~(2013) conjectured that $\chi''_{\Sigma}(G)\leq \Delta(G)+3$ for any simple graph with maximum degree $\Delta(G)$. We prove this bound to be asymptotically correct by showing that $\chi''_{\Sigma}(G)\leq \Delta(G)(1+o(1))$. The main idea of our argument relies on Przyby{\l}o's proof (2014) for neighbor sum distinguishing edgecoloring. 
Issue Date:  20170710 
Type:  Text 
URI:  http://hdl.handle.net/2142/98358 
Rights Information:  Copyright 2017 Sarah Loeb 
Date Available in IDEALS:  20170929 
Date Deposited:  201708 
This item appears in the following Collection(s)

Dissertations and Theses  Mathematics

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