Threshold Colorings of Prisms and the Petersen Graph

Abstract

Let $G$ be a graph, $r\ge t$ integers, and $N\subseteq E(G)$. An $(r,t)$-threshold-coloring of $G$ with respect to $N$ is a mapping $c:V(G)\to \{0,\dots ,r-1\}$ such that $|c(u)-c(v)|\le t$ for every $uv\in N$ and $|c(u)-c(v)|>t$ for every $uv\in E(G)\setminus N$. A graph is total threshold colorable if there exist integers $r,t$ such that for every $N\subseteq E(G)$, $G$ admits an $(r,t)$-threshold-coloring with respect to $N$. We show that every prism is total threshold colorable, and that the Petersen graph is total threshold colorable. In contrast to this fact we show that Moebius ladders are not total threshold colorable, from which it follows that there is no characterization of being total threshold colorable in terms of a finite set of forbidden subgraphs.