Coloring and covering problems on graphs

The \emph{separation dimension} of a graph $G$, written π(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} π_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 π_f(G)\le 3, with equality if and only if $G$ contains K₄. There is no stronger bound even for bipartite graphs, since π_f(K_m,m)=π_f(K_m+1,m)=\frac{3m}{m+1}. We also compute π_f(G) for cycles and some complete tripartite graphs. We show that π_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₄-free $n$-vertex graph maximizing π_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 π^\circ(G) be the number of circular orderings needed to separate all pairs, and let π_f^\circ(G) be the fractional version. Among our results: (1) π^\circ(G)=1 if and only $G$ is outerplanar. (2) π^\circ(G)\le2 when $G$ is bipartite. (3) π^\circ(K_n)\ge\log₂\log₃(n-1). (4) π_f^\circ(G)\le\frac{3}{2}, with equality if and only if K₄\subseteq G. (5) π_f^\circ(K_m,m)=\frac{3m-3}{2m-1}. 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 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent 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 4-coloring. 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 3-dynamically 10-choosable, 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 edge-coloring.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Loeb, Sarah Jane

Contributors dc:contributor

• West, Douglas B.
• Kostochka, Alexandr
• Yong, Alexander
• Molla, Theodore

• Graph coloring
• Graph covering

Statement dc:rights

• Copyright 2017 Sarah Loeb

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/98358

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/98358