Estimating Low Generalized Coloring Numbers of Planar Graphs
Document
Description
The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum
number of colors needed to color $V(G)$ such that no adjacent vertices
receive the same color. The coloring number $\col(G)$ of a graph
$G$ is the minimum number $k$ such that there exists a linear ordering
of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.
It is well known that the coloring number is an upper bound for the
chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is
a generalization of the coloring number, and it was first introduced
by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$
is the minimum integer $k$ such that for some linear ordering $L$
of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller
vertices $u$ (with respect to $L$) with a path of length at most
$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.
The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$
is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$
if and only if the distance between $x$ and $y$ in $G$ is $3$.
This dissertation improves the best known upper bound of the
chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$
of planar graphs $G$, which is $105$, to $95$. It also improves
the best known lower bound, which is $7$, to $9$.
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.
number of colors needed to color $V(G)$ such that no adjacent vertices
receive the same color. The coloring number $\col(G)$ of a graph
$G$ is the minimum number $k$ such that there exists a linear ordering
of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.
It is well known that the coloring number is an upper bound for the
chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is
a generalization of the coloring number, and it was first introduced
by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$
is the minimum integer $k$ such that for some linear ordering $L$
of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller
vertices $u$ (with respect to $L$) with a path of length at most
$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.
The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$
is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$
if and only if the distance between $x$ and $y$ in $G$ is $3$.
This dissertation improves the best known upper bound of the
chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$
of planar graphs $G$, which is $105$, to $95$. It also improves
the best known lower bound, which is $7$, to $9$.
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.