The name "Shukla graphs" is used in this work for four unit-distance graphs constructed by Shukla (2026ab). Their vertex counts, edge counts, chromatic numbers, and girths are summarized below.
| vertex count | edge count | chromatic number | girth | reference |
| 43 | 83 | 4 | 5 | Shukla (2026b) |
| 773 | 3817 | 5 | 3 | Shukla (2026a) |
| 5713 | 25482 | 5 | 3 | Shukla (2026a) |
| 8168 | 41556 | 5 | 3 | Shukla (2026a) |
The 43-vertex graph, illustrated above, has 83 edges and was constructed by Shukla (2026b). It has girth 5 and chromatic number 4. This example lowered the known upper bound on the number of vertices needed for a 4-chromatic unit-distance graph of girth 5 from the 45 of the Hochberg-O'Donnell star graph (Hochberg and O'Donnell 1996).
The graph is both 4-vertex-critical and 4-edge-critical. Shukla (2026c) supplies a 3-coloring after every single vertex deletion or edge deletion.
In Shukla's unit-distance embedding, two adjacent vertices are fixed at 
and 
. The remaining 82 coordinates
are the unique real solution in a specified rational box to 82 quadratic
equations, one for each of the other edges. The
resulting points are distinct, and the distance
between two of them is 1 exactly when they represent adjacent vertices
(Shukla 2026b).
The other three graphs have chromatic number 5 and contain triangles, so their girth is 3. Their unit-distance
embeddings lie inside open disks of radii 
, 
, and 
for 773, 5713, and 8168 vertices,
respectively (Shukla 2026a). The 773-vertex example
is vertex-critical. Shukla (2026a) supplies
explicit 5-colorings and machine-checkable certificates
of non-4-colorability for all three. These graphs address
size bounds under enclosing-disk constraints, whereas the
43-vertex example addresses a girth
constraint.
, 
and 
." 4 Nov 2026a.