Let $G$ be a uniquely $k$-colorable graph (for a definition, see https://en.wikipedia.org/wiki/Uniquely_colorable_graph). Is it true that we can always find a vertex $v$ such that $G-v$ is again uniquely $k$-colorable? The answer is certainly 'yes' when $k=2$ and for the family of uniquely $4$-colorable Apollonian networks, but I have not yet been able to find a general proof, or a counter-example.
2026-04-04 21:13:48.1775337228
Question about uniquely colorable graphs
56 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The answer turns out to be "no".
There exist uniquely 3-colorable graphs without triangles. The one on Mathworld (http://mathworld.wolfram.com/Uniquelyk-ColorableGraph.html) is incorrect (it has two different colorings as you can easily see by evaluating its chromatic polynomial at $k=3$ and dividing by $3!$), but there are others.
If the answer would be "yes" you can keep removing single vertices until you have three vertices left. Since there still is no triangle, the result cannot be uniquely $3$-colorable.