betaFeedback

WorksMathematics

A 43-vertex 4-chromatic unit-distance graph in the plane with girth 5

Abstract

We exhibit a set of 43 points in the Euclidean plane whose unit-distance graph has 83 edges, girth 5 and chromatic number 4. The smallest previously known 4-chromatic unit-distance graph of girth 5, due to Hochberg and O'Donnell (1996), has 45 vertices. The new graph is 4-critical, has trivial automorphism group, and has exactly 2n-3 edges; it is a Laman graph and its unit-distance realisation is infinitesimally rigid. The coordinates are algebraic numbers, specified as the unique real solution of an explicit system of 82 quadratic equations inside an explicit rational box. Every claim is certified by exact computation: existence and uniqueness of the realisation by a rational contraction-mapping certificate (independently re-checked with interval Krawczyk arithmetic), and non-3-colourability both by exhaustive search and by a DRAT proof verified with drat-trim.

Introduction

A unit-distance graph is a graph whose vertices are points of the plane, two points being adjacent when their Euclidean distance is exactly 1. The Hadwiger–Nelson problem asks for the chromatic number χ(R2)\chi(\mathbb{R}^2) of the graph on all points of the plane; it is known that 5≤χ(R2)≤75 \le\chi(\mathbb{R}^2) \le7 [1, 11].

Erdős asked whether 4-chromatic unit-distance graphs can avoid short cycles. Wormald [13] constructed a 4-chromatic unit-distance graph of girth 5 with 6448 vertices. O’Donnell later showed that 4-chromatic unit-distance graphs of every girth exist [10]. For small orders, Hochberg and O’Donnell [4] found 4-chromatic unit-distance graphs of girth 4 and girth 5 with 23 and 45 vertices respectively. The girth-4 record has since been lowered to 17 vertices by Exoo and Ismailescu [3]; we are not aware of any improvement of the 45-vertex girth-5 example.

Without the geometric restriction, the smallest 4-chromatic graphs of girth at least 5 have 21 vertices (Royle; see [2]). So the minimum order of a 4-chromatic unit-distance graph of girth 5 lies between 21 and 45.

In this note we lower the upper bound to 43.

Theorem 1. There is a set PP of 43 points in R2\mathbb{R}^2 whose unit-distance graph G43G_{43} has the following properties:

  1. G43G_{43} has 43 vertices and 83 edges, and its girth is 5;

  2. χ(G43)=4\chi(G_{43}) = 4;

  3. G43G_{43} is 4-critical: deleting any vertex or any edge leaves a 3-colourable graph;

The unit-distance realisation $P$ of $G_{43}$

Figure 1. The unit-distance realisation PP of G43G_{43}: the 43 points and the 83 unit edges, drawn to scale. Vertices are coloured by the 4-colouring of Table 1.

  1. G43G_{43} has degree sequence 315365743^{15}3^{6}5^{7}4 and trivial automorphism group;

  1. G43G_{43} has 2∣V∣−32|V|-3 edges and is a Laman graph, and the realisation PP is infinitesimally rigid.

The graph was found by a computer search; this note is concerned only with the graph and with the certificate of its properties.

The graph and its realisation

Label the vertices 0,1,…,420,1,\ldots,42. The 83 edges of G43G_{43} are

00–22, 00–2828, 00–2929, 11–2525, 11–3030, 11–3131, 22–1212, 22–3131, 33–66, 33–2424, 33–2828, 44–55, 44–1313, 44–1515, 55–77, 55–1010, 66–1111,

66–1212, 77–1111, 77–1414, 88–1010, 88–1313, 88–1818, 99–1717, 99–2020, 99–2121, 99–2727, 99–3636, 1010–1616, 1010–2323, 1010–2727, 1010–2828,

1010–3131, 1111–1616, 1111–2020, 1111–2929, 1111–3232, 1212–2323, 1212–3333, 1212–4141, 1313–3939, 1414–1818, 1414–3939, 1515–1818, 1515–1919,

1515–3131, 1515–3232, 1515–3333, 1616–1717, 1616–2525, 1616–2626, 1616–3333, 1616–3535, 1717–1919, 1919–2222, 2020–3131, 2020–3737, 2020–3939,

2121–2828, 2121–3535, 2222–2828, 2222–3737, 2323–3434, 2424–2929, 2424–3333, 2525–4040, 2626–3030, 2626–3838, 2727–4141, 2828–3232, 2828–3939,

3030–3939, 3131–3838, 3232–3434, 3232–4040, 3232–4141, 3333–3636, 3333–3939, 3434–3636, 3535–3737, 3838–4242, 3939–4242, 4040–4242.

An abstract drawing of $G_{43}$ with vertex labels

Figure 2. An abstract drawing of G43G_{43} with vertex labels (edges are not drawn at unit length). Vertex colours show the 4-colouring of Table 1; white is colour 0.

Exact coordinates. Put p0=(0,0)p_0=(0,0) and p2=(1,0)p_2=(1,0); the edge {0,2}\{0,2\} fixes position and orientation. The remaining 41 points give 82 unknown coordinates t=(t1,…,t82)t=(t_1,\ldots,t_{82}). Each of the 82 edges other than {0,2}\{0,2\} gives one equation

Fuv(t)=∥pu−pv∥2−1=0,F_{uv}(t)=\lVert p_u-p_v\rVert^2-1=0,

so F=(Fuv)F=(F_{uv}) is a square system of 82 quadratic polynomials with integer coefficients. Let c∈Q82c\in\mathbb{Q}^{82} be the vector of rational centres listed in Table 1 (given there to 16–17 significant digits; the exact rational values are in the supplementary files), let r=10−9r=10^{-9}, and let

vvxxyycolour
0000
10.4330899916763480.175177454542187361
2101
31.22674990310503350.00674210239160530962
41.033578176991139−0.0245756433330488742
51.399381442379761−0.955267843274050570
62.16303191455380080.357991294614806111
71.9849313733408456−0.14463150165626391
82.2506146807519531−0.110640864131209231
91.75822489305956681.95291005930278173
101.26129968959904450.035152991295277792
111.16552668852163530.428583957395854310
121.34804903507523830.937476329932225853
131.69799106035625090.722790077327497560
141.87461205868265710.849264694539972442
151.87416234235728260.517105315290847581
162.16491717051938080.463493332817283
172.57477889273408691.37564100105044231
182.86049860579097230.681849891637588910
191.5795009499901621.47270704396669630
201.99832417773254420.982161722451502572
211.59389274349726940.966504998174122170
220.63214075924367131.79287679423797441
232.1919707624073270.401010004673292180
241.31081252986791651.00320257565771760
251.22034685898867770.791802526375411710
261.26986631080794690.909457410439932222
271.37696812921033281.0284408710551641
280.60903443471454510.793143780995561383
290.312228413570436180.950007061952325091
300.303532602240695061.16674939182812350
310.998483271943468640.999998849767339660
321.40406134354562991.39971794318390422
332.19887962236281041.46291644234836522
342.40383216142710411.37830972717677391
352.49069315958364261.40894031967016691
362.68058044847672192.33925217374425820
371.62526192077657131.90996803436952130
381.44740096780850341.89357195944512551
391.20754276057542681.59426036669030591
400.404500887115420821.37007179771721571
410.410595619119340731.28558707798895290
420.561608382563537622.35765330568201170

Table 1. Box centres cc (vertices 0 and 2 are exact) and a 4-colouring.

X={t∈R82:∥t−c∥∞≤r}.X=\{t\in\mathbb{R}^{82}:\lVert t-c\rVert_\infty\le r\}.

Lemma 2. FF has exactly one zero t∗t^* in XX. At t∗t^* the Jacobian DF(t∗)DF(t^*) is nonsingular. Consequently every coordinate of t∗t^* is a real algebraic number.

Proof. Let BB be the explicit rational 82×8282\times82 matrix in the supplementary files (an approximate inverse of DF(c)DF(c)), and set T(t)=t−BF(t)T(t)=t-BF(t). Since FF is quadratic, each entry of DFDF has the form ±2(xu−xv)\pm2(x_u-x_v), and it changes by at most 4r4r on XX; each row of DFDF has at most four nonzero entries. Exact rational arithmetic gives

η:=∥BF(c)∥∞<4.95⋅10−15,q:=∥I−BDF(c)∥∞+16r∥B∥∞<7.25⋅10−7.\eta:=\lVert BF(c)\rVert_\infty<4.95\cdot10^{-15},\qquad q:=\lVert I-BDF(c)\rVert_\infty+16r\lVert B\rVert_\infty<7.25\cdot10^{-7}.

ends_mid=1 By the mean value theorem, ∥T(s)−T(t)∥∞≤q∥s−t∥∞\lVert T(s)-T(t)\rVert_{\infty} \le q\lVert s-t\rVert_{\infty} for s,t∈Xs,t \in X. Also ∥T(t)−c∥∞≤η+qr<r\lVert T(t)-c\rVert_{\infty} \le\eta+qr<r, so TT maps XX into itself. By the contraction mapping theorem TT has a unique fixed point t∗∈Xt^* \in X.

Since ∥I−B DF(c)∥∞<1\lVert I-B\,DF(c)\rVert_{\infty}<1, the matrix BB is invertible, so the fixed points of TT are exactly the zeros of FF in XX. The same estimate holds with DF(t∗)DF(t^*) in place of DF(c)DF(c), so DF(t∗)DF(t^*) is nonsingular.

A nonsingular zero is an isolated point of the complex variety {F=0}\{F=0\}. Because FF has rational coefficients, isolated points of this variety have algebraic coordinates.

Let P={p0,…,p42}P=\{p_0,\ldots,p_{42}\} be the points given by t∗t^*.

Lemma 3. The points of PP are pairwise distinct, and the unit-distance graph of PP is exactly G43G_{43}.

Proof. Every edge has length 1 by Lemma 2. For a pair u≠vu\ne v, interval bounds on ∥pu−pv∥2\lVert p_u-p_v\rVert^2 over the box XX, computed exactly in rational arithmetic, give

∥pu−pv∥2≥0.00173for all u≠v,∣∥pu−pv∥2−1∣≥0.00899for all non-edges {u,v}.\lVert p_u-p_v\rVert^2 \ge0.00173 \quad\text{for all }u\ne v,\qquad\bigl\lvert\lVert p_u-p_v\rVert^2-1\bigr\rvert\ge0.00899 \quad\text{for all non-edges }\{u,v\}.

So the points are distinct and no non-edge has length 1.

Proof of Theorem 1

(1) Girth. No edge has both ends with a common neighbour, so there are no triangles. No two vertices have two common neighbours, so there are no 4-cycles. The cycle 0,2,31,10,280,2,31,10,28 has length 5.

(2) Chromatic number. Table 1 gives a proper 4-colouring. To show χ(G43)>3\chi(G_{43})>3 we encode 3-colourability as a CNF formula with 129 variables: one clause per vertex saying that it gets some colour, and three clauses per edge. The SAT solver kissat (version 4.0.4) [6] reports this formula unsatisfiable and produces a DRAT proof of 1916 bytes. This proof was verified with drat-trim [12]. No symmetry breaking is used in this formula. Independently, an exhaustive DSATUR-style backtracking search, with the ends of the edge {0,2}\{0,2\} fixed to colours 0 and 1, visits 1957 nodes and finds no 3-colouring.

(3) Criticality. For each of the 43 vertices and each of the 83 edges, the deleted graph was 3-coloured explicitly by backtracking. All 126 colourings are included in the supplementary files, and each was checked to be proper.

(4) Degrees and automorphisms. The degree sequence is read off the edge list. A complete enumeration of the automorphisms (VF2 algorithm, as implemented in networkx) finds only the identity.

(5) Rigidity. The graph has 83=2⋅43−383=2\cdot43-3 edges. The (2,3)(2,3)-pebble game [5] confirms that every set of k≥2k\ge2 vertices spans at most 2k−32k-3 edges, so G43G_{43} is a Laman graph [8]. The rigidity matrix of the framework (G43,P)(G_{43},P), with the edge {0,2}\{0,2\} pinned, is 12DF(t∗)\frac{1}{2}DF(t^*). This matrix is nonsingular by Lemma 2, so the realisation is infinitesimally rigid.

Remark 4. Lemma 2 was checked twice, with independent code. The first check is the rational contraction certificate above, using exact Fraction arithmetic. The second is an interval Krawczyk test [7, 9] at 50 digits, carried out with an approximate inverse computed afresh from the Newton root. That test gives K(X)⊂int⁡XK(X)\subset\operatorname{int}X with ∥K(X)−c∥∞≤5⋅10−6r\lVert K(X)-c\rVert_{\infty}\le5\cdot10^{-6}r. A Newton iteration at 80 digits from cc converges to a root with residual below 10−8010^{-80} at distance 4.95⋅10−154.95\cdot10^{-15} from cc.

Remark 5. The realisation is tight in places: the smallest distance between two points of PP is about 0.0416, and the non-edge whose length is closest to 1 has squared length within 0.009 of 1. Because the system F=0F=0 is square and nonsingular, PP is locally the only realisation of G43G_{43} with these edge lengths, up to congruence. We have not looked for a closed-form expression of the coordinates.

Concluding remarks

The minimum order of a 4-chromatic unit-distance graph of girth 5 is now known to lie between 21 and 43. It would be interesting to narrow this gap. One step would be to decide whether any of the smallest 4-chromatic graphs of girth 5, which have 21 vertices (see [2]), is a unit-distance graph.

Data availability

The supplementary files contain:

  • the edge list;

  • the exact rational centres and the matrix BB;

  • the polynomial system;

  • the CNF formula and the DRAT proof;

  • two independent verification scripts.

They are available at https://doi.org/10.5281/zenodo.24036368.

Coordinates and colouring

Decimal values of the box centres; the exact rational centres are in the supplementary files. Each free coordinate of PP lies within 10−910^{-9} of the value shown. The last column is a proper 4-colouring.

References

  1. [1]A. D. N. J. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28 (2018), 18–31.arxiv.org/abs/1804.02385
  2. [2]G. Exoo and J. Goedgebuer, Bounds for the smallest \(k\)-chromatic graphs of given girth, Discrete Math. Theor. Comput. Sci. 21(3) (2019), #9.DOI
  3. [3]G. Exoo and D. Ismaileascu, Small order triangle-free 4-chromatic unit distance graphs, Geombinatorics 26 (2016).
  4. [4]R. Hochberg and P. O’Donnell, Some 4-chromatic unit distance graphs without small cycles, Geombinatorics 5 (1996), 137–141.
  5. [5]D. J. Jacobs and B. Hendrickson, An algorithm for two-dimensional rigidity percolation: the pebble game, J. Comput. Phys. 137 (1997), 346–365.DOI
  6. [6]A. Biere et al., Kissat SAT solver, version 4.0.4, https://github.com/arminbiere/kissat.
  7. [7]R. Krawczyk, Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing 4 (1969), 187–201.DOI
  8. [8]G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math. 4 (1970), 331–340.DOI
  9. [9]R. E. Moore, R. B. Kearfott and M. J. Cloud, Introduction to Interval Analysis, SIAM, 2009.DOI
  10. [10]P. O’Donnell, Arbitrary girth 4-chromatic unit distance graphs in the plane. I. Graph description; II. Graph embedding, Geombinatorics 9 (2000), 145–152 and 180–193.
  11. [11]A. Soifer, The Mathematical Coloring Book, Springer, 2009.DOI
  12. [12]N. Wetzler, M. J. H. Heule and W. A. Hunt Jr., DRAT-trim: efficient checking and trimming using expressive clausal proofs, in: Theory and Applications of Satisfiability Testing – SAT 2014, LNCS 8561, Springer, 2014, 422–429.DOI
  13. [13]N. C. Wormald, A 4-chromatic graph with a special plane drawing, J. Austral. Math. Soc. Ser. A 28 (1979), 1–8.DOI

Paper details

vlnc:W_djnetku6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents