Threshold Colorings of Prisms and the Petersen Graph

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) \rightarrow {0,\ldots,r-1}$suchthat$|c(u)-c(v)| \leq t$forevery$uv \in N$and$|c(u)-c(v)|>t$forevery$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$admitsan$(r,t)$-threshold-coloringwithrespectto$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.