Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane

MaRDI QIDQ5133129zbMATH OpenFDO

Authors Jaan Parts

Publication date 12 November 2020

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

zbMATH Keywords

5-chromatic unit-distance graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15)

Abstract: We introduce a new graph minimization method, in which it is required to preserve some graph property and there is an effective procedure for checking this property. We applied this method to minimize 5-chromatic unit-distance graphs and obtained a graph with 509 vertices and 2442 edges.

Recommendations

• Computing small unit-distance graphs with chromatic number 5
• Two small 6-chromatic unit-distance graphs in \(\mathbb{R}^3\)
• Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres
• The chromatic number of the plane is at least 5
• The chromatic number of the plane is at least 5: a new proof

Cited in

(4)

• All finite sets are Ramsey in the maximum norm
• Coloring distance graphs on the plane
• Computing small unit-distance graphs with chromatic number 5
• Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres

This page was built for publication: Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane

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