The term "Chilakamarri graphs" is used in this work for a set of graphs on 12, 24, and 47 vertices used in Chilakamarri's (1995) construction of a 47-vertex unit-distance graph with chromatic number 4 and girth 4. The three graphs are called the core, butterfly, and moth, respectively. All three are triangle-free unit-distance graphs with girth 4.
The Chilakamarri graph core has 12 vertices, 20 edges, and chromatic number 3. It is the starting point of the construction. Attaching two wings, each having 10 vertices and 12 edges, gives the Chilakamarri butterfly graph (Chilakamarri 1995, Soifer 2024). The wings share vertices with the core, so the resulting graph has 24 vertices and 44 edges.
The butterfly has chromatic number 3, but its 3-colorings satisfy an additional constraint. Two
designated vertices and
must receive the same color in every 3-coloring.
This makes the butterfly a building block for a graph with
chromatic number 4.
The Chilakamarri moth graph is obtained from two copies of the butterfly by contracting their designated vertices and adding an edge between their
two vertices
(Chilakamarri 1995, Soifer 2024). It has 47 vertices
and 89 edges. In any hypothetical 3-coloring,
both vertices
would have the color of the shared vertex
, contradicting the added edge.
A 4-coloring is obtained by giving one of these two
vertices a fourth color, so the moth has chromatic
number 4. Chilakamarri (1995) gave coordinates for a unit-distance
embedding and verified that the construction creates no triangles,
establishing girth 4.
For a time, the moth was the smallest known unit-distance graph with chromatic number 4 and girth 4. It was subsequently supplanted by smaller graphs, culminating in the presumed to be smallest possible 17-vertex Exoo-Ismailescu graph (Soifer 2024).
The core, butterfly, and moth have graph crossing number 4, 12, and 24, respectively.
The butterfly and moth are distinct from the 5-vertex butterfly graph and 6-vertex moth graph, respectively.
The three graphs are implemented in the Wolfram Language as GraphData["ChilakamarriGraphCore"], GraphData["ChilakamarriButterflyGraph"], and GraphData["ChilakamarriMothGraph"], respectively.