Genus, Skewness, Thickness and Coloring Theorems

Abstract

A conjecture by Albertson states that if $\chi (G)\ge n$, then $cr(G)\ge cr(K_n)$, where $\chi (G)$ is the chromatic number of $G$ and $cr(G)$ is the crossing number of $G$. This conjecture is true for $n\le 16$, but it remains open for $n\ge 17$.

In this paper, we consider the statements corresponding to this conjecture where the crossing number of $G$ is replaced with:
– the genus $\gamma (G)$ (the minimum genus of the orientable surface on which $G$ is embeddable),
– the skewness $\mu (G)$ (the minimum number of edges whose removal makes $G$ planar), and
– the thickness $\theta (G)$ (the minimum number of planar subgraphs of $G$ whose union is $G$).