1
$\begingroup$

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.

$\endgroup$

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.