{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/98358"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/98358","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Coloring and covering problems on graphs","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(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.","abstract_html":"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 K4. There is no stronger bound even for bipartite graphs, since πf(Km,m)=πf(Km+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 K4-free $n$-vertex graph maximizing πf(G) is Km,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(Kn)\\ge\\log2\\log3(n-1). (4) πf\\circ(G)\\le\\frac{3}{2}, with equality if and only if K4\\subseteq G. (5) πf\\circ(Km,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 NG(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) + \\sumuv \\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.","abstract_has_math":true,"creators":["Loeb, Sarah Jane"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["West, Douglas B.","Kostochka, Alexandr","Yong, Alexander","Molla, Theodore"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2017,"date_issued":"2017-09-29T17:56:39Z","date_published":"2017-09-29T17:56:39Z","updated_at":"2026-07-22T22:24:35Z","subjects":["Graph coloring","Graph covering"],"languages":["en"],"rights":["Copyright 2017 Sarah Loeb"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/98358","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["West, Douglas B.","Kostochka, Alexandr","Yong, Alexander","Molla, Theodore"]},{"key":"dc:creator","label":"Author","values":["Loeb, Sarah Jane"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2017-09-29T17:56:39Z","2017-07-10","2017-08"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph coloring","Graph covering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2017 Sarah Loeb"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/98358"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Coloring and covering problems on graphs"]}]}],"canonical_facts":{"dc:contributor":["West, Douglas B.","Kostochka, Alexandr","Yong, Alexander","Molla, Theodore"],"dc:creator":["Loeb, Sarah Jane"],"dc:date":["2017-09-29T17:56:39Z","2017-07-10","2017-08"],"dc:description":["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"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/98358"],"dc:language":["en"],"dc:rights":["Copyright 2017 Sarah Loeb"],"dc:subject":["Graph coloring","Graph covering"],"dc:title":["Coloring and covering problems on graphs"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:35Z"}