On the order of uniquely (k,m)-colourable graphs (Q923092): Difference between revisions

An m-admissible colouring of a finite simple graph G is a colouring of the vertices of G such that no m-clique of G is monocoloured. The m-th chromatic number of G is the least number \(\chi_ m(G)\) of colours such that G has an \(\chi_ m(G)\)-admissible colouring. A graph is called uniquely (k,m)-colourable if all m-admissible colourings in k colours induce the same partition of the vertex set of G. For \(k\geq 2\) and \(m\geq 3\), there exists a uniquely (k,m)-colourable graph of order n iff \(n\geq k(m-1)+m(k-1)\). All uniquely (2,m)-colourable graphs of order 3m-2 are determined, and the structure of all uniquely (k,m)- colourable graphs of order \(k(m-1)+m(k-1)\) is described.