5
$\begingroup$

For 4-chromatic unit distance graphs, the minimal example is the Moser spindle. If 3-cycles are disallowed, the minimal known example is the Exoo-Ismailescu 17 vertex graph.

If 4-cycles are disallowed, a nesting of 7-stars gives a 4-chromatic unit-distance graph with no 4-cycles. Is this the minimal number of vertices for such a graph?

Nested-7-star graph

$\endgroup$
1
$\begingroup$

There exist 4-chromatic unit distance graphs with the property above with as few as 12 vertices. Here is the edge set of one such graph:

\begin{equation*} \{1, 2\}, \{1, 3\}, \{1, 8\}, \{2, 4\}, \{2, 7\}, \{3, 6\}, \{3, 8\}, \{3, 11\}, \{4, 5\}, \{4, 7\}, \{4, 11\}, \\\{5, 10\}, \{5, 11\}, \{6, 9\}, \{6, 11\}, \{7, 9\}, \{7, 12\}, \{8, 10\}, \{8, 12\}, \{9, 12\}, \{10, 12\}. \end{equation*} There are 21 edges and it can be checked the chromatic number is 4, and the graph if $C_4$-free.

A unit-distance embedding is the following: \begin{align*} &[.0145594183, 1.740295066], [-.8188165902, 1.187588610], [.500000000, .8660254040],\\ &[-.9796710856, .2006104784], [-.3161017722, .9487252869], [1., 0.],\\ &[-.0444957030, .5547954644], [1.014419446, 1.723564110], [.8560373035, .9895831162],\\ &[.6703415551, .7846230022], [0., 0.], [.0292336482, 1.552073751] \end{align*} While this is the numerical data only, there is a symbolic (exact) embedding behind these numbers; the only problem is that it is quite complicated as most of the coordinates have minimal polynomials of degree 42. I am almost certain that there are no smaller graphs with the required properties.

enter image description here

(Added by Ed Pegg, a different embedding by Geoff Exoo)

nofour Unit-distance

$\endgroup$
1
  • $\begingroup$ The vertex on the lower right is at {1/2, -sqrt(11)/6 } $\endgroup$ – Ed Pegg Jul 31 '19 at 23:14

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.