Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres

DOI10.1016/J.DISC.2022.113106MaRDI QIDQ2675865zbMATH OpenOpenAlexWikidataFDO

Authors A. M. Neopryatnaya, E. A. Dergachev, Vsevolod Aleksandrovich Voronov

Publication date 26 September 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.11824

zbMATH Keywords

distance graphsHadwiger-Nelson problemSAT approach

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: This paper is devoted to the development of algorithms for finding unit distance graphs with chromatic number greater than 4, embedded in a two-dimensional sphere or plane. Such graphs provide a lower bound for the Nelson-Hadwiger problem on the chromatic number of the plane and its generalizations to the case of the sphere. A series of 5-chromatic unit distance graphs on 64513 vertices embedded into the plane is constructed. Unlike previously known examples, these graphs do not contain the Moser spindle as a subgraph. The construction of 5-chromatic graphs embedded in a sphere at two values of the radius is given. Namely, the 5-chromatic unit distance graph on 372 vertices embedded into the circumsphere of an icosahedron with a unit edge length, and the 5-chromatic graph on 972 vertices embedded into the circumsphere of a great icosahedron are constructed.

Recommendations

• Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane
• Odd-distance virtual edges in unit-distance graphs
• A small 6-chromatic two-distance graph in the plane
• Two small 6-chromatic unit-distance graphs in \(\mathbb{R}^3\)
• Computing small unit-distance graphs with chromatic number 5

Cites work

• A 15-colouring of 3-space omitting distance one
• A Problem of Leo Moser About Repeated Distances on the Sphere
• Chromatic numbers of spheres
• Coloring a Dodecahedron with Four Colors⁽¹⁾
• Computing small unit-distance graphs with chromatic number 5
• Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane
• scientific article; zbMATH DE number 3845607 (Why is no real title available?)
• scientific article; zbMATH DE number 3521120 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 2145248 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3068973 (Why is no real title available?)
• scientific article; zbMATH DE number 3098608 (Why is no real title available?)
• On graphs and rigidity of plane skeletal structures
• On lower bounds for the chromatic number of spheres
• On the chromatic number of a space
• On the chromatic numbers of spheres in \(\mathbb R^n\)
• On the space chromatic number
• The chromatic number of the plane is at least 5
• The chromatic number of the plane is at least 5 -- a human-veriviable proof
• The chromatic number of the plane is at least 5: a new proof
• The realization of distances within sets in Euclidean space
• The surface of a sufficiently large sphere has chromatic number at most 7
• Theory and Applications of Satisfiability Testing
• Two notions of unit distance graphs

Cited in

(5)

• Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane
• Odd-distance virtual edges in unit-distance graphs
• Coloring distance graphs on the plane
• On the chromatic number of 2-dimensional spheres
• On chromatic numbers of 3-dimensional slices

Describes a project that uses

Uses Software

• Treengeling
• Plingeling
• Lingeling
• MiniSat
• PaInleSS
• Glucose
• IGraph/M

This page was built for publication: Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2675865)