8
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ That's pretty much exactly what I was looking for - a place to start. :) Thanks! $\endgroup$
    – Sam Benner
    Jan 22, 2019 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.