Small unit-distance graphs in the plane

2019/05/19 by Globus, Aidan, Parshall, Hans
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1905.07829

Abstract

We prove that a graph on up to 9 vertices is a unit-distance graph if and only if it does not contain one of 74 so-called minimal forbidden graphs. This extends the work of Chilakamarri and Mahoney (1995), who provide a similar classification for unit-distance graphs on up to 7 vertices.

Related

• Computing Small Unit-Distance Graphs with Chromatic Number 5
• The Erdős unit distance problem for small point sets
• The Gray graph is a unit-distance graph
• Two notions of unit distance graphs
• The chromatic number of the plane is at least 5