2022-01-28T23:38:24Zhttps://keep.lib.asu.edu/oai/request
oai:keep.lib.asu.edu:node-1583142021-08-27T02:47:01Zoai_pmh:alloai_pmh:repo_items
158314 https://hdl.handle.net/2286/R.I.57262 http://rightsstatements.org/vocab/InC/1.0/ 2020 111 pages Doctoral Dissertation Academic theses Text eng Almulhim, Ahlam Kierstead, Henry Sen, Arunabha Richa, Andrea Czygrinow, Andrzej Fishel, Susanna Arizona State University Doctoral Dissertation Mathematics 2020 The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum<br/><br/>number of colors needed to color $V(G)$ such that no adjacent vertices<br/><br/>receive the same color. The coloring number $\col(G)$ of a graph<br/><br/>$G$ is the minimum number $k$ such that there exists a linear ordering<br/><br/>of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.<br/><br/>It is well known that the coloring number is an upper bound for the<br/><br/>chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is<br/><br/>a generalization of the coloring number, and it was first introduced<br/><br/>by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$<br/><br/>is the minimum integer $k$ such that for some linear ordering $L$<br/><br/>of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller<br/><br/>vertices $u$ (with respect to $L$) with a path of length at most<br/><br/>$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.<br/><br/>The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$<br/><br/>is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$<br/><br/>if and only if the distance between $x$ and $y$ in $G$ is $3$.<br/><br/>This dissertation improves the best known upper bound of the<br/><br/>chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$<br/><br/>of planar graphs $G$, which is $105$, to $95$. It also improves<br/><br/>the best known lower bound, which is $7$, to $9$.<br/><br/>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. Mathematics Theoretical mathematics Graph coloring Graph Theory Estimating Low Generalized Coloring Numbers of Planar Graphs