Threshold Colorings of Prisms and the Petersen Graph

MaRDI QIDQ6276316zbMATH OpenFDO

Authors Gašper Fijavž, Matthias Kriesell

Publication date 8 August 2016

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G$ be a graph, $rgeqt$ integers, and $NsubseteqE(G)$. An $(r,t)$-threshold-coloring of $G$ with respect to $N$ is a mapping $c:V(G)ightarrow0,ldots,r-1$ such that $|c(u)-c(v)|leqt$ for every $uvinN$ and $|c(u)-c(v)|>t$ for every $uvinE(G)setminusN$. A graph is total threshold colorable if there exist integers $r,t$ such that for every $NsubseteqE(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.

This page was built for publication: Threshold Colorings of Prisms and the Petersen Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6276316)