2022-01-28T23:38:24Zhttps://keep.lib.asu.edu/oai/requestoai:keep.lib.asu.edu:node-1583142021-08-27T02:47:01Zoai_pmh:alloai_pmh:repo_items158314
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