We call a graph $k$-colourable if there exists a colouring with $k$ colours of the vertices such that adjacent vertices have different colours. In the case the graph is regular, we can ask whether there exists a colouring with colours $\{1,\dotsc,k\}$ and constants $c_{11},\dotsc,c_{kk}\in\mathbb{N}$ such that $c_{ij}$ gives for each vertex with colour $i$ the number of neighbors with colour $j$.

My question is, has this or any comparable type of colouring/labeling been studied, or is this problem equivalent to something else? I was not successful in finding any literature on this topic. My goal is to prove that in some special case only the trivial colourings with $k\in\{1,n\}$ are possible, in case this is of any help.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.