On Connected Colourings of Graphs

Abstract

In this paper, first we introduce the concept of a $connected$ graph homomorphism as a homomorphism for which the inverse image of any edge is either empty or a connected graph, and then we concentrate on chromatically connected (resp. chromatically disconnected) graphs such as $G$ for which any $\chi (G)$-colouring is a connected (resp. disconnected) homomorphism to $K_{\chi (G)}$.

In this regard, we consider the relationships of the new concept to some other notions as uniquely-colourability. Also, we specify some classes of chromatically disconnected graphs such as Kneser graphs $KG(m,n)$ for which $m$ is sufficiently larger than $n$, and the line graphs of non-complete class II graphs.

Moreover, we prove that the existence problem for connected homomorphisms to any fixed complete graph is an NP-complete problem.