Timeline for Uniquely 4-colorable Unit Distance Graphs
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2016 at 6:53 | comment | added | joro | @PatDevlin Thanks. My original answer had error, edited. Another possibility is to take more copies of $G$, merge and rotate. Finally add an edge. | |
| Dec 15, 2016 at 6:10 | history | edited | joro | CC BY-SA 3.0 |
Fixed error
|
| Dec 15, 2016 at 6:02 | comment | added | joro | @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. | |
| Dec 15, 2016 at 0:32 | comment | added | Jan Kyncl | Why is $G'$ uniquely $4$-colorable? Can't you rename the three other colors in $G_2$ in five more ways? | |
| Dec 14, 2016 at 20:11 | comment | added | Pat Devlin | In fact, this shows something stronger. We can add any edge to the (full) unit distance graph without changing its chromatic number. | |
| Dec 14, 2016 at 20:06 | comment | added | Pat Devlin | 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$ | |
| Dec 14, 2016 at 16:15 | history | answered | joro | CC BY-SA 3.0 |