3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ A 1-vertex graph is still uniquely $k$-colorable for all $k$. The essence here is the partition in color classes. $\endgroup$ Dec 11, 2018 at 18:13
  • $\begingroup$ $K_1$ is uniquely $2$-colorable: every $2$-coloring induces the same partition in color classes. $\endgroup$ Dec 11, 2018 at 18:15

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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