Opuscula Math. 27, no. 1 (2007), 131-149

Opuscula Mathematica

# [r,s,t]-colourings of paths

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)

• Ingo Schiermeyer
• Institut für Diskrete Mathematik und Algebra, Technische Universität Bergakademie Freiberg, 09596 Freiberg