Circular Game Coloring of Signed Graphs

Pie Desire Ebode Atanhgana

REVIEW 5 major objections 4 minor 8 references

Circular Game Coloring of Signed Graphs

T0 review · 5 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper defines a signed circular coloring game, claims balanced signed graphs have the same circular game chromatic number as their unsigned underlying graphs, and asserts every other signature adds at most one color.

desk verdict A new signed circular game definition that is undone by its own k=2 vacuity and a false switching-invariance claim. read the letter →

arxiv 2505.21586 v1 pith:GNC4SIWG submitted 2025-05-27 math.CO

Pie Desire Ebode Atanhgana This is my paper

classification math.CO MSC 05C1505C2205C57

keywords signedgraphscirculargamechromaticnumbergraphcoloringbalancedantibalancedswitchingequivalencebipartite

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper defines a new invariant, the circular game chromatic number of a signed graph, by adapting a known coloring game to graphs whose edges carry a plus or minus sign. The main claim is that the sign of an edge barely changes the game's difficulty: for balanced signatures the signed number equals the unsigned value exactly, for antibalanced signatures it rises by at most one, and for bipartite graphs it is always 2 or 3 depending on balance. If correct, this would mean that balance, not the underlying graph's shape, is the feature that controls how many colors are needed, and that existing unsigned algorithms can be reused for balanced signed graphs. The proof strategy is to switch signatures into canonical all-positive or all-negative forms and then invoke known unsigned bounds.

What carries the argument

The load-bearing device is switching equivalence—flipping the sign of every edge incident to a single vertex, an operation that preserves the sign of every closed walk and therefore preserves balance classes (Lemma 2, following the characterization in [6]). The paper uses switching to replace an arbitrary balanced signature by the all-positive signature (G,+), reducing the signed game to the unsigned game; the same operation converts antibalanced signatures to (G,-). A supporting device is the fundamental cycle basis (Lemma 4), which determines switching classes from the signs of cycles outside a spanning tree and gives the count of switching classes used in the structural arguments.

What would settle it

Compute the signed circular game chromatic number of the 5-cycle in two switching-equivalent balanced signatures: all edges positive, and the signature obtained by switching one vertex (whose positive edges form a four-vertex path and whose negative edges are the remaining two edges). Under the paper's Definition 8, the first has value 2.5, while the second can be won with 2 colors; any such difference contradicts Proposition 25 and would refute Theorem 11(1) and Theorem 18(1).

Watch

Extended reading notes

Core claim

The paper establishes three results. First, for any balanced signed graph (G,σ), the signed circular game chromatic number equals the unsigned number χ_g^c(G) (Theorems 11(1) and 18(1)). Second, for antibalanced signed graphs, χ_g^c(G,σ) is sandwiched between χ_g^c(G) and χ_g^c(G)+1, and the upper bound is attained by odd cycles with the all-negative signature. Third, for bipartite graphs the value is exactly 2 when the signature is balanced and at most 3 otherwise, with explicit tight examples. These results are obtained by switching the signature to all-positive or all-negative form and then applying the unsigned framework developed in the paper's primary reference [1].

Load-bearing premise

The proofs assume that switching a vertex—flipping the signs of all edges incident to it—leaves the signed circular game chromatic number unchanged; under the paper's own edge-by-edge coloring rules, switching changes which edges demand separation and which demand closeness, so this invariance is not automatic and every balanced-case equality depends on it.

Editorial extensions

If this is right

For balanced signed graphs, the signed circular game chromatic number equals the unsigned value, so known algorithms and bounds for unsigned graphs transfer unchanged to balanced signatures.
For antibalanced non-bipartite graphs, the signed value is at most the unsigned value plus one, and odd cycles show this bound is tight.
For bipartite graphs, the dichotomy 2 versus 3 gives a simple decision rule: compute balance, and the answer is 2 if balanced and at most 3 otherwise.
The tight bipartite examples mean that some unbalanced bipartite signed graphs require strictly more colors than their unsigned counterparts, so the signature's effect is visible even without odd cycles.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct next step is to test whether the 'at most one extra color' bound survives when negative edges are interpreted with the complementary rule (colors far apart) instead of the paper's closeness rule, since the two interpretations give different games on the same signed graph.
The switching-based reduction, if it holds, would make the signed game reducible to the unsigned game for balanced graphs; this suggests the computational complexity of balanced signed instances matches the unsigned case, which the paper already claims in its algorithmic section.
The bipartite dichotomy could be turned into a practical balance test: compute balance first, and the answer is either 2 or 3, so for sparse signed bipartite graphs the invariant is cheaply bounded without solving the full game.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear [Colleague],

The punchline: this paper's main theorems are refuted by its own Definition 8. The balanced-graph equality chi_g^c(G,sigma) = chi_g^c(G) (Theorems 11(1) and 18(1)) fails because switching invariance (Proposition 25) is false. On C5, the all-positive signature has chi_g^c at least 5/2, since any final coloring is a circular coloring. Switch one vertex; the signature is still balanced but the positive subgraph is P4. At k=2 the negative-edge condition |c(u)-c(v)| <= d or >= kd-d holds for every pair of colors, so negative edges never constrain play; Salome wins with colors 0,d,0,d on the path and any color on the switched vertex. Two balanced signatures on the same graph therefore have different chi_g^c, and the proof route to the headline result collapses.

What is actually new: Definition 8 is a real attempt to define a signed circular game, and the paper correctly identifies switching as the key structural tool. The early material on balance and switching (Propositions 1-6) is standard but accurately stated. That is the credit.

The soft spots are extensive and not all of equal weight. The k=2 vacuity alone refutes Example 15, Example 22, Theorem 18(3), and Lemma 13(2): any signed graph whose positive subgraph is bipartite has value 2. There are internal contradictions: Lemma 13 says a tree with a negative edge has value 4, Theorem 17 says a negative P4 forces 3, and Theorem 27 says every tree equals the unsigned value. Proposition 21(1) says every bipartite graph has only two switching classes, while Proposition 5 gives 2^{|E|-|V|+1}, which is 4 for K_{2,3}. The proofs are frequently assertions: Theorem 11(3) invokes a balanced/antibalanced decomposition that does not exist; Theorem 18(2) says it 'modifies' Lin-Zhu's Theorem 3.2 without showing the modification; Theorem 29 attributes NP-hardness to [1] with no location.

Who this is for: nobody, in the current form. It has a new definition but no verified result. A serious referee would waste time on claims that are false under the paper's own rules. Send it back.

Recommendation: reject; do not send to peer review. If the author revisits the definition or proves switching invariance under a corrected rule, there might be a small note worth considering, but not as it stands.

Referee Report

5 major / 4 minor

Summary. The paper defines a signed analog of the circular game chromatic number, χ_g^c(G,σ), with a coloring game in which positive edges require circular distance in [d,kd-d] and negative edges require distance at most d or at least kd-d. It claims that balanced signed graphs have χ_g^c(G,σ)=χ_g^c(G), that antibalanced signed graphs satisfy χ_g^c(G)≤χ_g^c(G,σ)≤χ_g^c(G)+1 with tightness on odd cycles, and that bipartite signed graphs have a 2-versus-3 dichotomy. These claims are justified through switching equivalence (Proposition 25), a decomposition of signatures into balanced and antibalanced parts, and an extension of Lin-Zhu's unsigned framework. The paper also contains algorithmic consequences for balanced graphs, trees, and treewidth-bounded graphs.

Significance. The question of how edge signs affect game coloring is natural, and the paper correctly identifies switching classes and Zaslavsky-type lemmas as useful tools. However, the central invariant is not switching-invariant under the paper's own Definition 8, and the negative-edge rule is vacuous at k=2. These two facts invalidate the main theorems and the bipartite dichotomy. The paper's strength is its organization and the clarity of its structural lemmas about signed graphs; the weakness is that the game-theoretic claims built on those lemmas are false as stated. Because the main results collapse, the paper cannot be accepted in its current form.

major comments (5)

[§5, Proposition 25; also Theorem 11(1) and Theorem 18(1)] Switching invariance is false under Definition 8. Consider C5 with the all-positive signature; since any completed coloring is a circular coloring, χ_g^c(C5,+) ≥ 5/2. Now switch vertex 1. The signature remains balanced, with positive edges 23,34,45 and negative edges 12,15. At k=2, kd−d = d, so the negative-edge condition |c(u)−c(v)| ≤ d or ≥ d is satisfied by every pair of colors; the negative edges impose no constraint. The positive subgraph is the path P4, which is 2-colorable in the game, so Salome wins with k=2. Thus χ_g^c(C5,σ)=2 for this balanced signature, contradicting Proposition 25. Since Theorem 11(1) and Theorem 18(1) are proved exclusively through switching to (G,+), those theorems collapse.
[§3, Definition 8; §4, Theorem 18(3); §3, Example 22; §3, Lemma 13] At k=2 the negative-edge condition in Definition 8 is vacuous, because kd−d = d and every color pair satisfies |c(u)−c(v)| ≤ d or |c(u)−c(v)| ≥ d. This directly refutes the claimed tight values. For Example 22, the alternating K_{2,3} has a positive subgraph of matching edges and negative edges elsewhere; at k=2 the negative edges are unconstrained, so a proper 2-coloring of the positive subgraph is a winning final coloring and Salome wins with k=2, not k=3. Similarly, Lemma 13(2) asserts that every signed tree with at least one negative edge has χ_g^c=4; the all-negative star has no positive constraints at k=2, so χ_g^c=2. The dichotomy in Corollary 12 and Theorem 18(3) is therefore false.
[§3, Theorem 11(1) and its proof] The proof begins by claiming that 'the coloring constraints for (G,σ) are at least as restrictive as for (G,+)'. This is not true: the negative-edge condition is not a refinement of the positive-edge condition. For k=4,d=1, a color pair at distance 2 satisfies the positive-edge condition but violates the negative-edge condition; at k=2 every pair satisfies the negative-edge condition. Thus the inequality χ_g^c(G,σ) ≤ χ_g^c(G,+) is not established by the given argument. The same proof also appeals to a switching equivalence that, as shown above, does not preserve the game number.
[§2 and §4, definitions of antibalanced; Proposition 20] The paper defines a signed graph to be antibalanced if every cycle has negative sign. Under that definition no signed graph containing an even cycle can be antibalanced, since an even number of negative signs multiplies to positive. Yet Proposition 20 asserts that antibalanced is equivalent to switchability to (G,−), which would make an all-negative C4 antibalanced. The two statements are inconsistent. This affects Theorem 18(2) and the bipartite classification in Proposition 21, and it also makes the phrase 'antibalanced' used throughout the paper ambiguous.
[§5, Theorems 26, 27, 29 and Proposition 30] The algorithmic results inherit the false premises. Theorem 26 reduces balanced signed graphs to the unsigned case by switching to (G,+); since switching does not preserve χ_g^c, the O(n^3) algorithm is not justified. Theorem 27 reduces signed trees to unsigned trees by the same invalid switching argument. Theorem 29's NP-hardness reduction only treats all-positive signatures, so it does not establish hardness for arbitrary signatures, and Proposition 30's factor-2 approximation relies on Theorem 11, whose proof is unsupported. These statements should be re-examined after the invariant is redefined.

minor comments (4)

[§1, Introduction] The text contains an apparent drafting artifact: 'This formulation maintains the original meaning while presenting the information in a more narrative and cohesive manner. Let me know if you'd like any refinements!' This sentence should be removed.
[§3, Example 15] The formula 'χ_g^c(C_n,σ)=2+1/k where k depends on the game strategy' is not meaningful as written. The circular chromatic number of C5 is 5/2, so the dependence on n and the distinction between the game parameter k and the index n should be stated precisely.
[§3, Theorem 11(2)] The notation χ_g^c(G,−) is used for 'antibalanced' signatures, but because the paper's definition of antibalanced conflicts with the standard one, the statement is ambiguous; an all-negative C4 is a concrete case where the terminology as defined in §2 and as used in Proposition 20 give different classifications.
[§3, proof of Theorem 11(3)] The phrase 'any signature can be decomposed into balanced and antibalanced components through switching' is used without a formal definition or proof; a concrete decomposition operation is needed even if the switching-invariance issue were repaired.

Circularity Check

1 steps flagged · score 8.0 of 10

The balanced-case equality is circular: Theorem 18(1) proves chi_g^c(G,sigma)=chi_g^c(G) by invoking switching invariance, while Proposition 25 merely asserts that invariance with no derivation from Definition 8.

self definitional [Proposition 25; invoked in proofs of Theorem 11(1) and Theorem 18(1)]
"Since switching preserves the signs of all closed walks, the coloring constraints for adjacent vertices remain equivalent up to sign changes. The game chromatic number depends only on the relative coloring constraints, which are preserved under switching."

Definition 8 defines legal moves edgewise by sign, so switching changes which constraint applies to each edge. The proof of Proposition 25 does not derive invariance from Definition 8; it simply asserts that the constraints are preserved. Theorem 18(1) then concludes chi_g^c(G,sigma)=chi_g^c(G) 'since switching preserves... the game coloring constraints.' Thus the balanced-case equality is the same statement as the assumed switching invariance, not a consequence of balance plus Lin-Zhu. The premise is also false under Definition 8: two balanced signatures on C5 give game values 5/2 and 2, so the central claim has no independent derivation.

full rationale

This manuscript is not a fitting exercise, and its citation of Lin-Zhu [1] is external rather than self-citational, so the usual self-citation concerns do not apply. The central circularity is structural: Theorem 18(1) and Theorem 11(1) reduce the balanced signed-graph game to the unsigned game by switching the signature to (G,+). The only support for this reduction is Proposition 25, whose proof repeats the desired conclusion ('the coloring constraints ... are preserved under switching') without connecting it to the edgewise rule of Definition 8. Because switching changes which edges are positive and which are negative, the closed-walk argument in Proposition 25 does not address the game rule. The failure is not hypothetical: at k=2 the negative-edge condition of Definition 8 is vacuous, so switching one vertex of C5 changes the positive subgraph from C5 to P4 and changes the circular game chromatic number from 5/2 to 2, even though both signatures are balanced. Hence the headline equality chi_g^c(G,sigma)=chi_g^c(G) for balanced graphs is not an independent theorem; it is the assumed switching invariance restated. The bipartite dichotomy of Corollary 12 and Theorem 18(3) is similarly affected: the same k=2 vacuity makes all-negative bipartite graphs automatically 2-colorable in the (2,d)-game, so the claimed tight value 3 is not forced by the paper's own definition. Because the central claim reduces to an unproved, false premise that is effectively its own conclusion, the circularity score is 8.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numerical free parameters and no invented entities: this is pure combinatorics, and the players Salome and Andjiga are just renamed actors of the standard game. The load-bearing content is carried by assumptions that are false or unproved under Definition 8: switching invariance (Proposition 25), the asserted balanced/antibalanced decomposition (Theorem 11(3)), and the ad hoc negative-edge rule whose k=2 regime is vacuous. The correct standard facts (Harary's balance theorem, Lemma 2, Proposition 5 counting 2^{|E|-|V|+k} switching classes) do not rescue the main claims; indeed Proposition 21(1), which allows only two switching classes on bipartite graphs, contradicts Proposition 5 for K_{2,3}.

assumptions (4)

ad hoc to paper Switching a signature preserves the signed circular game chromatic number (Proposition 25, Remark 7).
Load-bearing for Theorems 11(1) and 18(1) and for the algorithms in Section 5. The stated reason, that switching preserves closed-walk signs, does not imply invariance of an edgewise-defined game. Refuted by Definition 8: switching one vertex of the all-positive C5 yields a balanced signature whose positive subgraph is P4, with chi_g^c = 2, while chi_g^c(C5,+) >= 2.5.
ad hoc to paper Every signature can be decomposed into balanced and antibalanced components by switching (proof of Theorem 11(3)).
No such decomposition is defined. A general signature is neither balanced nor antibalanced, and switching does not decompose a signature; this 'observation' carries Theorem 11(3).
ad hoc to paper The negative-edge rule in Definition 8, with k >= 2 and the quantification 'for all d >= 1' in Definition 9, is the right signed analog.
At k=2 the rule is satisfied by every color pair, so negative edges are unconstrained and every signed graph with bipartite positive subgraph has chi_g^c = 2. The claimed bipartite dichotomy and tight value 3 are artifacts of this rule choice, not consequences of the game's structure. No comparison is made with existing signed circular coloring conventions.
domain assumption The unsigned circular game chromatic number decision problem is NP-hard, and O(n^3) and linear-time exact algorithms for it exist, all attributable to [1].
Theorem 29, Theorem 26 and Theorem 27 rely on these attributions, citing [1] (Lin-Zhu 2009) without theorem numbers. [1] is a bounds-theory paper; the NP-hardness and algorithm claims are unverified, and the reduction in Theorem 29 is three lines.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Circular Game Coloring of Signed Graphs." pith.science (2026). https://pith.science/paper/GNC4SIWG

@misc{pith2026250521586,
  author       = {Pith},
  title        = {Pith review of: Circular Game Coloring of Signed Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GNC4SIWG}},
  note         = {Machine review of arXiv:2505.21586}
}

abstract

We extend the theory of circular game chromatic numbers to signed graphs by defining the invariant $\chi_c^g(G,\sigma)$ for signed graphs $(G,\sigma)$. Our analysis establishes tight bounds dependent on the structural properties of the underlying graph $G$ and its signature $\sigma$. Building on the foundational framework of Lin and Zhu \cite{LinZhu2009}, we demonstrate that the circular game chromatic number of a balanced signed graph $(G, \sigma)$ equals that of its underlying graph $G$, i.e., $\chi_c^g(G,\sigma) = \chi_c^g(G)$. For antibalanced signed graphs, we prove that $\chi_c^g(G,\sigma)$ does not exceed the chromatic number of $G$ plus one, with tightness demonstrated for odd cycles. A dichotomy emerges for bipartite graphs: $\chi_c^g(G,\sigma)$ equals $2$ when the graph is balanced, and otherwise remains bounded above by $3$. These results rely on switching equivalence principles (Lemma \ref{lem:Zaslavsky}) and critical properties of fundamental cycles (Lemma \ref{lem:ForcingTree}), adapting classical techniques from unsigned graph theory to the signed context. We further highlight open questions regarding computational complexity and planar graph extensions, creating new bridges between combinatorial game theory and signed graph structural analysis.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 5 canonical work pages

[1]

Lin, W., & Zhu, X. (2009). Circular game chromatic num- ber of graphs . Discrete Mathematics, 309(13), 4495-4501. https://doi.org/10.1016/j.disc.2009.02.011

work page doi:10.1016/j.disc.2009.02.011 2009
[2]

K¨ onig, D. (1936). Theorie der endlichen und unendlichen Graphen . Leipzig: Akademische Verlagsgesellschaft

work page 1936
[3]

Zaslavsky, T. (1998). A bibliography of signed graphs and related math- ematics. Electronic Journal of Combinatorics, Dynamic Surveys, DS8. https://doi.org/10.37236/27 14

doi:10.37236/27 1998
[4]

Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2), 143-146. https://doi.org/10.1307/mmj/1028989917

arXiv 1953
[5]

Zaslavsky, T. (1981). Characterizations of signed graphs . Journal of Graph Theory, 5(4), 401-406. https://doi.org/10.1002/jgt.31900504 10

work page doi:10.1002/jgt.31900504 1981
[6]

Zaslavsky, T. (1982). Signed graphs . Discrete Applied Mathematics, 4(1), 47-74. https://doi.org/10.1016/0166-218X(82)90033-6

doi:10.1016/0166-218x(82)90033-6 1982
[7]

Hansen, P. (1978). Labelling algorithms for balance in signed graphs . In P. Hansen (Ed.), Studies on Graphs and Discrete Programming (pp. 21 5-228). North-Holland. https://doi.org/10.1016/S0167-5060(08)70349 -1

work page doi:10.1016/s0167-5060(08)70349 1978
[8]

Harary, F., & Kabell, J. A. (1980). Balanced signed graphs and groupoid identities . Czechoslovak Mathematical Journal, 30(105), 422-427. https://doi.org/10.21136/CMJ.1980.102179 15

work page arXiv 1980

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Lin, W., & Zhu, X. (2009). Circular game chromatic num- ber of graphs . Discrete Mathematics, 309(13), 4495-4501. https://doi.org/10.1016/j.disc.2009.02.011

work page doi:10.1016/j.disc.2009.02.011 2009

[2] [2]

K¨ onig, D. (1936). Theorie der endlichen und unendlichen Graphen . Leipzig: Akademische Verlagsgesellschaft

work page 1936

[3] [3]

Zaslavsky, T. (1998). A bibliography of signed graphs and related math- ematics. Electronic Journal of Combinatorics, Dynamic Surveys, DS8. https://doi.org/10.37236/27 14

doi:10.37236/27 1998

[4] [4]

Harary, F. (1953). On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2), 143-146. https://doi.org/10.1307/mmj/1028989917

arXiv 1953

[5] [5]

Zaslavsky, T. (1981). Characterizations of signed graphs . Journal of Graph Theory, 5(4), 401-406. https://doi.org/10.1002/jgt.31900504 10

work page doi:10.1002/jgt.31900504 1981

[6] [6]

Zaslavsky, T. (1982). Signed graphs . Discrete Applied Mathematics, 4(1), 47-74. https://doi.org/10.1016/0166-218X(82)90033-6

doi:10.1016/0166-218x(82)90033-6 1982

[7] [7]

Hansen, P. (1978). Labelling algorithms for balance in signed graphs . In P. Hansen (Ed.), Studies on Graphs and Discrete Programming (pp. 21 5-228). North-Holland. https://doi.org/10.1016/S0167-5060(08)70349 -1

work page doi:10.1016/s0167-5060(08)70349 1978

[8] [8]

Harary, F., & Kabell, J. A. (1980). Balanced signed graphs and groupoid identities . Czechoslovak Mathematical Journal, 30(105), 422-427. https://doi.org/10.21136/CMJ.1980.102179 15

work page arXiv 1980