First non-trivial upper bound on circular chromatic number of the plane

DOI10.1016/J.ENDM.2015.06.097MaRDI QIDQ322359zbMATH OpenOpenAlexFDO

Authors Konstanty Junosza-Szaniawski

Publication date 14 October 2016

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

zbMATH Keywords

coloring of the planecircular coloringNelson-Hadwiger problem

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: We consider circular version of the famous Nelson-Hadwiger problem. It is know that 4 colors are necessary and 7 colors suffice to color the euclidean plane in such a way that points at distance one get different colors. In $r$-circular coloring we assign arcs of length one of a circle with a perimeter $r$ in such a way that points at distance one get disjoint arcs. In this paper we show the existence of $r$-circular coloring for $r=4+frac4sqrt33approx6.30$. It is the first result with $r$-circular coloring of the plane with $r$ smaller than 7. We also show $r$-circular coloring of the plane with $r<7$ in the case when we require disjoint arcs for points at distance belonging to the internal $[frac1011,frac1211]$.

Recommendations

• Upper bound on the circular chromatic number of the plane
• Circular Coloring the Plane
• The chromatic number of the plane is at least 5
• scientific article; zbMATH DE number 1552837
• scientific article; zbMATH DE number 653246

Cites work

• Circular Coloring the Plane
• Circular chromatic number: A survey
• Star chromatic number
• -unit distance graphs

Cited in

(3)

• Circular Coloring the Plane
• Upper bound on the circular chromatic number of the plane
• A finite graph approach to the probabilistic Hadwiger-Nelson problem

This page was built for publication: First non-trivial upper bound on circular chromatic number of the plane

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