A planar signed graph with circular chromatic number five

arXiv:2610.34118 · math.CO · Submitted 2026-10-25 · Read on arXiv

math.CO

Submitted: 2026-10-25

Updated: 2026-10-25

License: http://creativecommons.org/licenses/by/4.0/

The gist: A circular r-coloring of a signed graph maps its vertices to a circle of circumference r at least2, with the endpoints of negative edges at circular distance at least 1 and those of positive edges at…

Abstract

A circular r-coloring of a signed graph maps its vertices to a circle of circumference r at least2, with the endpoints of negative edges at circular distance at least 1 and those of positive edges at most r/2-1; the circular chromatic number is the infimum of such r. We construct a simple planar signed triangulation on 85 vertices with circular chromatic number exactly 5. This improves the lower bound on the supremum of the circular chromatic numbers of simple planar signed graphs from 14/3 to 5, giving a partial answer to a question posed by Naserasr, Wang, and Zhu.

Related papers