Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
František Kardoš, Jonathan Narboni, Reza Naserasr, Zhouningxin Wang · SIAM Journal on Discrete Mathematics · 2023
Abstract. A circular [Formula: see text]-coloring of a signed graph [Formula: see text] is an assignment [Formula: see text] of points of a circle [Formula: see text] of circumference [Formula: see text] to the vertices of [Formula: see text] such that for each positive edge [Formula: see text] of [Formula: see text] the distance of [Formula: see text] from [Formula: see text] is at least 1 and for each negative edge [Formula: see text] the distance of [Formula: see text] from the antipode of [Formula: see text] is at least 1. The circular chromatic number of [Formula: see text], denoted [Formula: see text], is the infimum of [Formula: see text] such that [Formula: see text] admits a circular [Formula: see text]-coloring. This notion was recently defined by Naserasr, Wang, and Zhu, who, among other results, proved that for any signed [Formula: see text]-degenerate simple graph [Formula: see text] we have [Formula: see text]. For [Formula: see text], examples of signed [Formula: see text]-degenerate simple graphs of circular chromatic number [Formula: see text] are provided. But for [Formula: see text] only examples of signed 2-degenerate simple graphs of circular chromatic number arbitrarily close to 4 are given, noting that these examples are also signed bipartite planar graphs. In this work we first observe the following restatement of the 4-color theorem: If [Formula: see text] is a signed bipartite planar simple graph where vertices of one part are all of degree 2, then [Formula: see text]. Motivated by this observation, we provide an improved upper bound of [Formula: see text] for the circular chromatic number of a signed 2-degenerate simple graph on [Formula: see text] vertices and an improved upper bound of [Formula: see text] for the circular chromatic number of a signed bipartite planar simple graph on [Formula: see text] vertices. We then show that each of the bounds is tight for any value of [Formula: see text].