On \delta^(k)-colouring of Powers of Paths and Cycles

Abstract

In a proper vertex colouring of a graph, the vertices are coloured in such a way that no two adjacent vertices receive the same colour, whereas in an improper vertex colouring, adjacent vertices are permitted to receive same colours subjected to some conditions. An edge of an improperly coloured graph is said to be a bad edge if its end vertices have the same colour. A near proper colouring is a colouring which minimises the number of bad edges by restricting the number of colour classes that can have adjacency among their own elements. The $\delta^{(k)}$- colouring is a near proper colouring of $G$ consisting of $k$ given colours, which minimises the number of bad edges by permitting at most one colour class to have adjacency among the vertices in it. In this paper, we determine the number of bad edges of powers of Paths $(P_{n})$ and powers of Cycles $(C_{n})$.

Keywords

• improper colouring
• near proper colouring
• \delta^(k)-colouring
• bad edges.