The Frankl-Hubai-Pálvölgyi graph is a name used here for the 35-vertex, 106-edge graph illustrated above. It encodes the 34-point
unit-distance graph 
of Frankl, Hubai, and Pálvölgyi (2023), which
has no proper coloring with four colors when its
distinguished origin is allowed two colors. The 35-vertex encoding replaces the origin
by two coincident vertices, joins them by a distance-0 edge, and gives both copies
the origin's unit-distance neighbors. Thus, an ordinary proper
coloring assigns two distinct colors to the origin while excluding both colors
from its neighbors. The resulting abstract graph has chromatic
number 5.
Frankl et al. (2023) described 
as the first example found whose relevant coloring property
could be checked quickly without a computer. They used it in a proposed route to
a human-verifiable lower bound of 5 for the Hadwiger-Nelson
problem.
The Frankl-Hubai-Pálvölgyi graph will be implemented in a future version of the Wolfram Language as GraphData["FranklHubaiPalvolgyiGraph"].
