Menu
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})\).