Return to search

Estimating Low Generalized Coloring Numbers of Planar Graphs

abstract: 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. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2020

Identiferoai:union.ndltd.org:asu.edu/item:57262
Date January 2020
ContributorsAlmulhim, Ahlam (Author), Kierstead, Henry (Advisor), Sen, Arunabha (Committee member), Richa, Andrea (Committee member), Czygrinow, Andrzej (Committee member), Fishel, Susanna (Committee member), Arizona State University (Publisher)
Source SetsArizona State University
LanguageEnglish
Detected LanguageEnglish
TypeDoctoral Dissertation
Format111 pages
Rightshttp://rightsstatements.org/vocab/InC/1.0/

Page generated in 0.0018 seconds