5
$\begingroup$

A graph is "unit distance" if it can be embedded in the plane in such a way that whenever two vertices are connected by an edge, their distance is $1$.

A graph is uniquely $4$-colorable if there is a unique way (up to renaming of colors) of coloring its vertices with $4$ colors in such a way that no two adjacent vertices have the same color, and if no such coloring with $3$ colors exists.

Question: Is there finite graph that is both uniquely $4$-colorable and unit distance?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Complete graphs $K_n$ are examples for $n=1\ 2\ 3\ $ (am I right?). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 13, 2016 at 20:42
  • 1
    $\begingroup$ @WłodzimierzHolsztyński No, at least 4 colors should be required. I have edited the question to make this clear. $\endgroup$
    – verifying
    Commented Dec 13, 2016 at 22:47
  • $\begingroup$ (Perhaps a phrase "with less than 4" should be more complete than "with 3"). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Dec 14, 2016 at 0:58
  • $\begingroup$ Of course this question by now is obsolate since de Grey has found a 5-chromatic unit distance graph. $\endgroup$
    – domotorp
    Commented Aug 3, 2018 at 5:50

1 Answer 1

Reset to default
5
$\begingroup$

EDIT the original answer was wrong, thanks to Jan Kyncl for pointing the mistake, hopefully it is fixed now.

I think this is open, since existence will improve the lower bound of chromatic number for unit distance graphs from $4$ to $5$ almost surely.

Assume uniquely $4$ colorable finite unit distance graph $G$ exists. Color it with colors $a,b,c,d$. Take two copies of $G$: $G_1$ and $G_2$. For vertices colored $a$, $a_1 \in G_1, a_2 \in G_2$ merge $a_1$ and $a_2$ to vertex $A$ to get unit distance graph $G'$ with the property that all vertices in $G_1,G_2$ which are colored $a$ have the same color in all $4$ colorings of $G'$. For vertices $a_1' \in G_1, a_2' \in G_2$ colored with the $a$ color, rotate $G_2$ with center $A$ trying to get $a_1',a_2'$ at distance $1$. The triangle inequality is enough. If you can do this, add edge $(a_1',a_2')$ to get unit distance graph, which is not $4$ colorable. I think such four vertices exist with high probability and comment by Pat Devlin confirms this.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This is in fact a complete proof of what you say (i.e., you could use it to show $\chi \geq 5$ for unit distance graph). Say $u$ and $v$ must be colored the same. Then make your two copies of $G$ and put vertices corresponding to $u$ in the same spot. Rotate until the vertices corresponding to $v$ have unit distance (ok by intermediate value theorem). $\qed$ $\endgroup$
    – Pat Devlin
    Commented Dec 14, 2016 at 20:06
  • $\begingroup$ In fact, this shows something stronger. We can add any edge to the (full) unit distance graph without changing its chromatic number. $\endgroup$
    – Pat Devlin
    Commented Dec 14, 2016 at 20:11
  • $\begingroup$ Why is $G'$ uniquely $4$-colorable? Can't you rename the three other colors in $G_2$ in five more ways? $\endgroup$
    – Jan Kyncl
    Commented Dec 15, 2016 at 0:32
  • $\begingroup$ @JanKyncl Thanks, you are right. $G'$ is unit distance, but not uniquely 4 colorable. Looks like the main idea can be saved: In $G'$ all vertices which are colored $a$ in $G_1$ and $G_2$ are of the same color in all 4 colorings of $G'$, so the two new vertices must be colored $a$ in addition. $\endgroup$
    – joro
    Commented Dec 15, 2016 at 6:02
  • $\begingroup$ @PatDevlin Thanks. My original answer had error, edited. Another possibility is to take more copies of $G$, merge and rotate. Finally add an edge. $\endgroup$
    – joro
    Commented Dec 15, 2016 at 6:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .