Uniquely \(n\)-colorable and chromatically equivalent graphs (Q1608645)

A graph is uniquely \(k\)-colorable if any proper \(k\)-coloring of the vertices induces the very same partition on the vertex set. The main result in the paper is a concrete construction of uniquely \(n\)-colorable graph on \(2n\) and on \(2n+1\) vertices for \(n>2\). The key idea is that the complement of a uniquely \(k\)-colorable graphs has a unique clique cover of \(k\) cliques, so the complement of a path on \(2n\) vertices and the complement of a \((2n+1)\)-cycle with a short chord suffice. If we substitute each vertex by a clique in the path and cycle examples then we still get complements of uniquely \(k\)-colorable graphs, but this case with more vertices. The author also constructs chromatically equivalent but nonisomorphic uniquely \((n+1)\)-colorable graphs on \(2n+2\) vertices and on \(2n+3\) vertices.