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.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C12 Distance in graphs
PDF BibTeX Cite