[r,s,t]-colourings of paths

Marta Salvador Villà
Ingo Schiermeyer

Abstract. The concept of \([r,s,t]\)-colourings was recently introduced by Hackmann, Kemnitz and Marangio [A. Kemnitz, M. Marangio, \([r,s,t]\)-Colorings of Graphs, Discrete Math., to appear] as follows: Given non-negative integers \(r\), \(s\) and \(t\), an \([r,s,t]\)-colouring of a graph \(G=(V(G),E(G))\) is a mapping \(c\) from \(V(G) \cup E(G)\) to the colour set \(\{1,2,\ldots ,k\}\) such that \(|c(v_i)-c(v_j)| \geq r\) for every two adjacent vertices \(v_i\), \(v_j\), \(|c(e_i)-c(e_j)| \geq s\) for every two adjacent edges \(e_i\), \(e_j\), and \(|c(v_i)-c(e_j)| \geq t\) for all pairs of incident vertices and edges, respectively. The \([r,s,t]\)-chromatic number \(\chi_{r,s,t}(G)\) of \(G\) is defined to be the minimum \(k\) such that \(G\) admits an \([r,s,t]\)-colouring. In this paper, we determine the \([r,s,t]\)-chromatic number for paths.

Keywords: total colouring, paths.

Mathematics Subject Classification: 05C15, 05C38.

Full text (pdf)