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?

$\endgroup$
  • 1
    $\begingroup$ Complete graphs $K_n$ are examples for $n=1\ 2\ 3\ $ (am I right?). $\endgroup$ – Włodzimierz Holsztyński Dec 13 '16 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 Dec 13 '16 at 22:47
  • $\begingroup$ (Perhaps a phrase "with less than 4" should be more complete than "with 3"). $\endgroup$ – Włodzimierz Holsztyński Dec 14 '16 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 Aug 3 '18 at 5:50
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.

| cite | improve this answer | |
$\endgroup$
  • 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 Dec 14 '16 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 Dec 14 '16 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 Dec 15 '16 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 Dec 15 '16 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 Dec 15 '16 at 6:53

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.