A planar signed graph with circular chromatic number five
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality