# What is known about graphs that permit only one colouring?

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).

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. The lower bound for the number of edges is achieved at any $$(k-1)$$-tree (alternatively maximal graph of treewidth $$k-1$$).