2026-09-20T20:02:24Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/98358 2023-07-11 col_2142_16340 col_2142_5131 com_2142_16339 com_2142_8903 com_2142_5130

West, Douglas B. Kostochka, Alexandr Yong, Alexander Molla, Theodore Loeb, Sarah Jane 2017-09-29T17:56:39Z 2017-09-29T17:56:39Z 2017-07-10 2017-08 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(n-1)$. (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{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. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms The student, Sarah Loeb, accepted the attached license on 2017-07-10 at 12:01. The student, Sarah Loeb, submitted this Dissertation for approval on 2017-07-10 at 12:06. This Dissertation was approved for publication on 2017-07-10 at 17:35. DSpace SAF Submission Ingestion Package generated from Vireo submission #11363 on 2017-09-29 at 11:29:29 Made available in DSpace on 2017-09-29T17:56:39Z (GMT). No. of bitstreams: 3 LOEB-DISSERTATION-2017.pdf: 647913 bytes, checksum: 538fdcc54f2ac36f68879bdd350811ac (MD5) LICENSE.txt: 4207 bytes, checksum: 2b53faa7d740fec129f209a4cc526060 (MD5) PROQUEST_LICENSE.txt: 4553 bytes, checksum: 39df65dab1de182e4f961ba584f1e8ec (MD5) Previous issue date: 2017-07-10 application/pdf http://hdl.handle.net/2142/98358 en Copyright 2017 Sarah Loeb Graph coloring Graph covering Coloring and covering problems on graphs text text Mathematics Mathematics University of Illinois at Urbana-Champaign Dissertation Ph.D.