Some graphs ($K\_n$ or $K\_n$ minus any one edge, for instance) only permit one minimal colouring up to different labels of the colours. Is there anything known about these kind of graphs? I can think of a number of examples of such graphs (mostly just $K\_{n,m}$ minus an edge or two), but I can't think of any general statements I can make about them.


I was just wondering if there was any prior research into this as I couldn't find anything. It could be that it's trivial (in which case I'd be interested in whether there's anything known about the number of minimal colourings).



What is known about graphs that permit only one colouring?
It's a bit hard to give a comprehensive answer without knowing exactly what sort of properties you are after, but here is a start. Such graphs are called uniquely colorable graphs (see [here](http://mathworld.wolfram.com/Uniquelyk-ColorableGraph.html) and [here](https://en.wikipedia.org/wiki/Uniquely_colorable_graph)). For the case of two colors they are characterized as the connected bipartite graphs, but for higher numbers of colors no such characterization is known.


In a uniquely $k$-colorable graph of $n$ vertices, the number of edges is at least $(k-1)n-\binom{k}{2}$, but otherwise they don't have to be extremely dense as your examples suggest. In fact for any $n$ there exist graphs with $n$ vertices that are uniquely 3-colorable [and have no triangles](https://www.sciencedirect.com/science/article/pii/0012365X9390220N). The lower bound for the number of edges is achieved at any [$(k-1)$-tree](https://en.wikipedia.org/wiki/K-tree) (alternatively maximal graph of treewidth $k-1$).


