On the Nordhaus-Gaddum Problem for the $n$-Path-Chromatic Number of a Graph

Abstract

Let $\mathcal{G}(p)$ denote the class of simple graphs of order $p$. For a graph $G$, the complement of $G$ is denoted by $\overline{G}$. For a positive integer $n$, the $n$-path-chromatic number ${\chi }_n(G)$ is the least number of colours that can be associated to the vertices of $G$ such that not all the vertices on any path of length $n$ receive the same colour. The Nordhaus-Gaddum Problem for the $n$-path-chromatic number of $G$ is to find bounds for ${\chi }_n(G)+{\chi }_n(\overline{G})$ and ${\chi }_n(G)\cdot {\chi }_n(\overline{G})$ over the class $\mathcal{G}(p)$. In this paper, we determine sharp lower bounds for the sum and the product of ${\chi }_n(G)$ and ${\chi }_n(\overline{G})$. Furthermore, we provide weak upper bounds for ${\chi }_2(G)+{\chi }_2(\overline{G})$ and ${\chi }_2(G)\cdot {\chi }_2(\overline{G})$.