Circular chromatic number of signed graphs

Background

• Circular coloring extends ordinary circular coloring while retaining chromatic information: χ(G) − 1 < χc(G) ≤ χ(G) and χ(G) = ⌈χc(G)⌉.Thus the circular chromatic number refines the ordinary chromatic number by encoding additional structural information.Source: §1 · p. 2

Definitions

• Signed circular coloring assigns vertices points on a circle, requiring positive-edge endpoints to be separated and negative edges to be separated from an antipode.The signed graph consists of a graph with each edge labeled positive or negative; circular distance is measured along the shorter arc.Source: §1 · p. 2
• The signed circular chromatic number of a simple graph is the maximum circular chromatic number over all its signatures.When every edge is positive, the signed parameter recovers the ordinary circular chromatic number.Source: §1 · p. 3

Relations to signed coloring

• For signed graphs, 0-free 2k-colorability is equivalent to circular 2k-colorability.The equivalence is established by mapping signed colors to symmetric positions on a circle of circumference 2k.Source: §1 · p. 3

Contributions

• The paper studies basic properties, relations between signed and ordinary circular chromatic numbers, and bounds for large-girth, bipartite planar, d-degenerate, outerplanar, and series-parallel graphs.The stated program includes graph classes with arbitrarily large girth and bipartite planar graphs.Source: §1 · p. 4
• A signed planar simple graph is constructed with circular chromatic number 4 + 2/3, improving the Kardos–Narboni example and addressing a prior 4-colorability conjecture.The paper states that the exact value of the relevant planar supremum remains open, lying between 4 + 2/3 and 6.Source: §1 · p. 4

Circular and discrete colorings

• A circular r-coloring maps vertices to [0,r) while enforcing distance constraints determined by positive and negative edge signs.For rational r=p/q, colors can be discretized using finitely many intervals, with p required to be even so antipodal colors are well defined.Source: §2 · p. 4
• For even p and q≤p/2, a (p,q)-coloring assigns colors in {0,…,p−1} subject to positive-edge distances and antipodal negative-edge constraints.The circular chromatic number is equivalently the infimum of p/q for which such a coloring exists.Source: §2 · p. 5

Homomorphism formulations

• Signed circular coloring is equivalent to an edge-sign preserving homomorphism to an appropriate signed circular clique.The construction uses a signed clique with positive edges for distances between q and p−q and negative edges for the complementary antipodal range.Source: §2 · pp. 5–6
• A signed graph is circularly r-colorable exactly when it admits an edge-sign preserving homomorphism to the corresponding infinite signed circular clique.For rational r=p/q with even p, the finite signed clique embeds into the infinite target, connecting discrete and continuous formulations.Source: §2 · p. 6

Switching invariance

• Switching preserves circular colorability: switching a vertex set and shifting its colors by p/2 yields a corresponding (p,q)-coloring, so χc(G,σ′)=χc(G,σ).Thus switching-equivalent signed graphs have the same circular chromatic number.Source: §2 · pp. 6–7

Switching homomorphisms

• Switching homomorphisms combine switching equivalence with edge-sign preserving homomorphisms and provide another definition of signed circular chromatic number.This framework also supports the characterization of (2k,1)-colorability by switching so that the positive-edge subgraph becomes k-colorable.Source: §2 · p. 7

Switching equivalence

• By Zaslavsky’s theorem [23], two signed graphs are switching equivalent exactly when they have the same set of negative cycles.Switching preserves cycle signs, and the switching-equivalence class is determined by all cycle signs.Source: §2 · p. 7

Switching homomorphisms

• A signed graph admits a switching homomorphism to another exactly when a graph homomorphism preserves the signs of every closed walk and its image.Equivalently, vertices and edges can be mapped while preserving adjacencies, incidences, and closed-walk signs.Source: §2 · p. 8

Signed-cycle notation

• For a non-zero integer ℓ, Cℓ denotes a cycle of length |ℓ| whose sign agrees with ℓ; for example, C−4 is a negative cycle of length 4.Source: §2 · p. 8

Negative loops

• Adding or deleting negative loops does not change circular chromatic number, but negative loops matter as switching-homomorphism targets because negative edges may collapse onto looped vertices.Two vertices joined by a negative edge can map to the same vertex when that target vertex is incident with a negative loop.Source: §2 · p. 8

Tight orientations

• A circular coloring induces tight arcs and tight paths or cycles, recording edges whose signed color separation is exactly one.These objects organize the section’s structural analysis of circular colorings.Source: §3 · p. 8

Tight-cycle characterization

• χc(G, σ) = r exactly when (G, σ) is circular r-colorable and every circular r-coloring contains a tight cycle.If the tight-arc digraph is acyclic, the coloring can be perturbed to obtain a smaller circular parameter.Source: §3 · pp. 8–9

Arithmetic constraints

• Every nonforest signed graph contains a cycle whose positive and negative edge counts satisfy the section’s stated arithmetic relation, yielding finitely many candidate circular chromatic numbers for fixed order.The relation follows by traversing a tight directed cycle around the coloring circle.Source: §3 · pp. 9–10

Algorithmic consequences

• For an n-vertex signed graph, χc(G, σ) is attained among finitely many candidates, so the defining infimum is a minimum and an algorithm can determine it.The problem remains NP-hard, and no feasible algorithm exists unless P=NP.Source: §3 · p. 10

The case χc = 2

• Any signed graph with an edge has χc(G, σ) ≥ 2, with equality exactly when it is switching equivalent to (G, −).The section also notes that deciding whether χc(G, σ) = 2 is easy.Source: §3 · p. 10

Signed cores

• The section defines sign-preserving and switching cores and establishes that each finite signed graph has a unique switching core up to isomorphism, contained in a sign-preserving core.It then proves corresponding core identifications for the signed complete-cycle constructions treated later in the section.Source: §3 · p. 10

• The passage is a fragment referring to “p;q” and a proper subgraph, without a complete claim.Source: §3 · p. 11

Large-girth constructions

• For every k, g ≥ 2, and ε > 0, there is a graph of girth at least g whose signed circular behavior reaches the bound established for large-girth k-chromatic graphs.The construction begins with a graph of chromatic number at most k and produces a signature that is not circular (2kp, p+1)-colorable.Source: §4 · p. 12
• The construction uses bipartite q-augmented k-ary trees with girth at least g, whose existence is guaranteed for all positive k, q, and g.Augmenting edges connect each leaf to selected ancestors, and the resulting graph is used as the structural host for the signed construction.Source: §4 · p. 12
• The constructed graph has chromatic number at most k because the level map θ(v) = ℓ(v)(mod k) is a proper k-coloring.Its girth is at least g because each added edge can be replaced by a path of length at most 2k in the host graph, whose girth is at least 2kg.Source: §4 · p. 13
• The signed graph is not circular (2kp, p+1)-colorable: every presumed coloring yields an f-path contradicting the sign-dependent distance condition on an added edge.The contradiction follows from the edge-sign construction and the resulting bound on the circular distance between the relevant labels.Source: §4 · p. 13

Limits and tightness

• The section notes unresolved scope and tightness issues: the constructed graphs are shown only to have chromatic number at most k, and it remains unknown whether the relevant finite k-chromatic large-girth examples exist.A separate construction involving paired positive and negative edges shows tightness for a bound, but has girth 2 because of parallel edges.Source: §4 · pp. 11, 13

Critical graphs of large girth

• For k-critical graphs of sufficiently large girth, ordinary circular chromatic number is at most k −1 + ε, while signed circular chromatic number is at most 2k −2 + ε.The signed bound follows as a consequence of the ordinary bound and the relation developed in the section.Source: §4 · p. 13

• Signed indicators are triples I = (Γ, u, v), where Γ is a signed graph with two distinct terminals.Source: §5 · p. 14
• Replacing each edge of G with an indicator copy produces G(I), while Ω(I+, I−) uses separate indicators for positive and negative edges.Source: §5 · p. 14
• A color pair is feasible when a circular r-coloring of the indicator assigns prescribed colors to its terminals; translation and reflection symmetries recover all feasible pairs from pairs beginning at 0.Source: §5 · p. 14
• The set Z(I, r) records possible terminal distances and is nonempty exactly when the indicator graph has circular chromatic number at most r.Source: §5 · p. 14
• Indicator replacement lemmas transfer circular colorings between a base graph and its gadget expansion by requiring each base-edge distance to lie in the indicator's feasible-distance set.Source: §5 · p. 15
• For every ε > 0, the constructed signed bipartite planar simple graph Γ satisfies χc(Γ) > 4 − 2ε, showing that this family has circular chromatic numbers arbitrarily close to 4.Source: §5 · pp. 16–17

Signed d-degenerate graphs

• For d = 2, the limiting circular chromatic number is 4; for odd integer d, the bound is tight on signed complete graphs; and Ωd is d-degenerate with χc(Ωd) = d + 2.Source: §6 · p. 18

Signed outerplanar graphs

• The signed outerplanar simple graph (F, σ) in Figure 5 has circular chromatic number 3.A positive triangle gives the lower bound, while the absence of a switching homomorphism to the relevant target excludes a circular 3-coloring.Source: §6 · p. 19, Figure 5 · p. 19

Signed bipartite planar graphs

• The signed bipartite planar class has χc(SBP) = 4, although it remains unknown whether a signed bipartite planar simple graph attains this bound.A further improvement depending on the shortest negative-cycle length is deferred to forthcoming work.Source: §6 · p. 20

Signed planar graphs

• By Proposition 6.1, 5-degenerate graphs satisfy χc(SP) ≤ 6, and the section constructs a signed planar simple graph Ω with χc(Ω) = 4 + 2.Extending the construction in, it organizes the construction into gadgets and starts with a mini-gadget similar to the gadget of.Source: §6 · p. 20

Planar construction gadgets

• Lemma 6.5 characterizes the mini-gadget’s circular (4 + α)-colorings for 0 ≤ α < 2, including extension from any three suitably separated prescribed colors.The proof constrains the interval containing the three terminals and uses the positive triangle a,b,c to rule out incompatible placements.Source: §6 · p. 21

Construction and result

• The construction replaces each of four negative facial triangles in a signed Wenger graph with a switching of the mini-gadget, producing Ẇ.The resulting graph is then used to define Γ by adding a negative edge uv and I = (Γ, u, v).Source: §6 · pp. 21–22
• Lemma 6.7 establishes that Ẇ has a property similar to signed indicators, enabling the subsequent construction and circular-coloring argument.The proof of Lemma 6.7 is deferred to the next section.Source: §6 · pp. 21–22
• 14/3: Theorem 6.8 gives a signed planar simple graph Ω = K4(I) with χ_c(Ω) = 14/3.The graph is formed from the indicator I and K4.Source: §6 · p. 22

Initial interval restrictions

• Assuming η < 4, the proof partitions possible color intervals and uses signed-edge distance constraints to restrict φ(z), φ(x2), and φ(x3).Claim 7.2 derives interval restrictions, while subsequent subcases eliminate all possible placements through positive- and negative-edge contradictions.Source: §7 · pp. 22–25

Symmetry and switching

• The proof does not use x1 in its initial argument, and switching at {w, x2, x3, x4, x5} transfers the conclusion to an isomorphic signed subgraph.Thus the same obstruction applies after exchanging the roles of x2 and x3 with x4 and x5.Source: §7 · p. 26

Case analysis

• The argument updates the allowable ranges of φ(xi) case by case, using negative triangles and positive edges to force narrow, largely disjoint intervals.Figures 10–13 depict these successive range updates and the resulting cyclic-order constraints.Source: §7 · pp. 26–28

Final contradiction

• The intervals Iw, I5, I4, I3, and I2 have length less than 1 and force the colors of the positive 5-cycle wx5x4x3x2 into cyclic order.Because the circle has length 3−ε, two consecutive vertices of this all-positive cycle receive colors at distance less than 1, contradicting the coloring condition.Source: §7 · p. 29
• A parallel range analysis places φ(w), φ(x4), φ(x5), φ(x1), and φ(x2) cyclically on the circle, contradicting the positive edges of the 5-cycle wx4x5x1x2.This supplies a second terminal contradiction for the remaining case.Source: §7 · p. 29

Range restrictions

• Based on choices of φ(z) and φ(t), four subcases update ranges of φ(xi)’s, with positive and negative edges further restricting ranges of φ(x3), φ(x5), φ(x2), and φ(x4).Source: §7 · pp. 29–30

Case contradiction

• In one case, the disjoint intervals for φ(w), φ(x2), φ(x1), φ(x5), and φ(x4) force two consecutive vertices of the positive 5-cycle wx2x1x5x4 to have distance less than 1.This contradicts the requirement on every positive edge of the cycle.Source: §7 · p. 31
• In the remaining case, interval restrictions and the positive edge x3x4 similarly contradict the all-positive 5-cycle wx2x3x4x5.The proof concludes that these contradictions complete Lemma 6.7.Source: §7 · p. 32

8 Questions and Remarks

• The paper’s circular coloring is rotation-invariant and therefore more faithful to ordinary graph circular coloring than the asymmetric definition introduced in.The definition in uses a fixed diameter, making antipodal colors and endpoint colors special; the paper regards this lack of rotational symmetry as undesirable.Source: §8 · p. 32

8.1 Jaeger-Zhang conjecture and extensions

• For ij ∈ Z2, g_ij(G, σ) is the length of a shortest closed walk whose negative-edge count has parity i and total edge count has parity j.Source: §8.1 · p. 32

8.2 Hadwiger conjecture and extensions

• The Odd-Hadwiger conjecture states that if (G, −) has no (K_k+1, −)-minor, then χ_c(G, +) ≤ k, extending Catlin’s signed formulation.Signed minors are obtained by deleting vertices or edges, contracting positive edges, and switching; the paper also asks for the best bound on χ_c(G, −σ) under the same minor exclusion.Source: §8.2 · p. 33

8.3 Signed planar graphs

• For signed planar multigraphs, the digon has χ_c(D) = 4, its indicator construction yields χ_c(K_4(D)) = 8, and the class satisfies χ_c(SPM) = 8.Positive loops prevent circular colorings, whereas adding a negative loop does not change the circular chromatic number; the exact class value for signed planar simple graphs remains open.Source: §8.3 · p. 34
• The paper notes that the conjectured value 4 for signed planar simple graphs was disproved in, while the exact class value and improved bounds remain open.The particular K_4(I) gadget cannot improve the lower bound because its circular chromatic number is exact.Source: §8.3 · pp. 34–35

8.4 Girth and planarity

• For signed planar graphs of girth at least 10, a result of gives a switching homomorphism to (K_4, e), whose circular chromatic number is 3, yielding Theorem 8.7’s upper bound; tightness is unknown.The section further asks for analogous bounds in other graph classes and for refined bounds specified by lower limits on g_01, g_10, and g_11.Source: §8.4 · p. 35

8.5 Spectrum

• For non-trivial K4-minor-free graphs, characterizes the rational circular chromatic numbers as exactly those in [2, 8/3].Source: §8.5 · p. 35
• It remains open whether each rational number between 8/3 and 10/3 occurs as the circular chromatic number of a K4-minor-free signed graph.The discussion also records an upper-bound extension to 10/3 for K4-minor-free simple graphs.Source: §8.5 · p. 35
• Spectrum questions for series-parallel graphs of fixed girth, planar graphs, and other graph families are identified as natural directions for signed analogues.Related circular-chromatic spectrum questions for these unsigned families were studied in.Source: §8.5 · p. 35