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 Answer 1

Reset to default
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, 2019 at 23:14

You must log in to answer this question.

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