# zbMATH — the first resource for mathematics

A 40-vertex $$4$$-chromatic triangle-free unit distance graph. (English) Zbl 0847.05050
Paul Erdös posed the question: are there any 4-chromatic subgraphs with no short cycles in the unit distance graph in the plane, that is, the graph whose vertices are all points in the real plane and whose edges connect all pairs of points distance 1 apart? The author constructs a 40-vertex 4-chromatic subgraph with no 3-cycles.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles 05C12 Distance in graphs
##### Keywords:
unit distance graph; plane