Fractional balanced chromatic number and arboricity of planar (signed) graphs

Cyril Pujol; Huan Zhou; Lan Anh Pham; Reza Naserasr

REVIEW 2 major objections 5 minor 13 references

Fractional balanced chromatic number and arboricity of planar (signed) graphs

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

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

Pith's one-line read A planar signed simple graph exists whose fractional balanced chromatic number is strictly larger than 2.

desk verdict A likely correct counterexample to the Bonamy–Kardos–Kelly–Postle conjecture, but the proof of the key mini-gadget lemma is too sketchy to certify. read the letter →

arxiv 2505.16808 v1 pith:HEYGOP2J submitted 2025-05-22 math.CO

Reza Naserasr , Lan Anh Pham , Cyril Pujol , Huan Zhou This is my paper · ORCID

classification math.CO MSC 05C1505C1005C22

keywords fractionalbalancedchromaticnumbersignedgraphsplanararboricitycoloringfragmentgadgetconjecturegraph

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

For a signed graph, a balanced set is a vertex set inducing no negative cycle, and a fractional balanced coloring places nonnegative weights on balanced sets so each vertex receives total weight at least 1; the minimum total weight is the fractional balanced chromatic number. This paper constructs a planar signed simple graph whose fractional balanced chromatic number is strictly larger than 2. Since that number is always at most the fractional arboricity of the underlying graph, the same construction refutes the conjecture that every planar graph has fractional arboricity at most 2. Iterating the gadget pushes the lower bound on the supremum for planar signed simple graphs to $83/41$, with a concrete first member at $2+2/85$.

What carries the argument

The load-bearing object is a signed planar gadget built from the classical fragment construction, together with the triangle property. A facial triangle has the triangle property if, in every balanced $(2k,k)$-coloring, a negative triangle receives each color at least once and a positive triangle receives each color at most twice. Lemma 3 claims that any facial triangle of a plane signed graph can be completed by adding a vertex inside the face, and a mini-gadget for positive triangles, so that the triangle property holds, and Lemma 4 then forces the distinguished endpoints $u$ and $v$ of the gadget to share no color in any balanced $(2k,k)$-coloring. That no-common-color conclusion is what makes the global construction exceed two colors.

What would settle it

Search exhaustively for a balanced $(2,1)$-coloring of the 64-vertex signed planar graph obtained by identifying the three $z$-vertices in the construction; if any assignment of two colors to the vertices has each color class free of negative cycles, then the claimed nonexistence of $(2k,k)$-colorings fails at $k=1$ and the main theorem collapses.

Watch

Extended reading notes

Core claim

The paper's central result is that a balanced $(2k,k)$-coloring cannot exist for a certain finite planar signed graph, so its fractional balanced chromatic number exceeds 2. The proof's key step shows that in the gadget $<span class="math">$\widehat{W}''$</span> the distinguished endpoints $u$ and $v$ must receive disjoint color sets in every such coloring; placing copies of the gadget on the three edges of a triangle then demands $3k$ colors from a palette of $2k$, a contradiction. Because balanced color classes are more restrictive than acyclic ones, this also yields a planar graph with fractional arboricity above 2, refuting the conjecture of $<span class="math">$[2]$</span>. The paper then computes the exact value $2+2/85$ for the first iterated graph, proves a limiting lower bound of $83/41$, and exhibits an explicit planar graph with fractional arboricity $2+2/25$.

Load-bearing premise

The proof depends on the claim that every facial triangle can be equipped with a small completion that forces the triangle property in every balanced $(2k,k)$-coloring; if that enforcement ever fails, the conclusion that the gadget's distinguished endpoints share no color no longer follows.

Editorial extensions

If this is right

Conjecture 1 is false: there is a planar graph with $a_f(G)>2$, and the construction can be made concrete with $a_f(W_1)=2+2/25$.
The fractional balanced chromatic number of planar signed simple graphs has no upper bound of 2; its supremum is at least $2+1/41$.
In the iterative family, the first nontrivial member has exact fractional balanced chromatic number $2+2/85$, so the obstruction appears already in a finite explicit graph.
No graph built from a negative triangle by the two allowed operations needs more than $83/41$ colors in the fractional sense, so the bound $83/41$ is the ceiling for this construction method.

Reading between the lines

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

The exact supremum of the fractional balanced chromatic number for planar signed simple graphs is not determined here; it lies somewhere between $83/41$ and the general upper bound $5/2$.
Because the same gadget drives both parameters, the unsigned counterpart has a gap as well: $a_f(W_1)=2+2/25$ is a concrete planar graph exceeding 2, but the supremum of planar fractional arboricity could be larger.
A direct computer verification of Lemma 3 on the 64-vertex graph for small $k$ would be a natural independent test of whether the triangle-completion step is as robust as stated.
If the triangle property can be enforced on other face types, the same construction pattern could be adapted to signed graphs on higher-genus surfaces or to other families with similar balancing constraints.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

Short version: this is a serious paper with a genuinely new counterexample to a plausible conjecture, but the proof of the key lemma is sketched in a way that I can't fully verify from the text. It should be refereed, not desk-rejected, but the authors need to fill a real gap.

What's new: the construction using Wenger's gadget to get a planar signed graph with χ_fb > 2, the iterative lower bound to 83/41, and the explicit (52,25)-coloring showing fractional arboricity 2+2/25 for W1. The paper is self-contained and the main idea is nice. The list of maximal balanced sets in Lemma 8 is checkable, and the coloring tables are concrete.

Where I'm nervous: Lemma 3 is central. The negative-triangle part (adding a vertex to make (K4,−)) is fine. The positive-triangle part is one sentence: 'if a color c appears in all three u_i, then it can appear in none of the u'_j which is not possible.' That 'which is not possible' depends on the inner negative triangle having the triangle property, but that property is only asserted. The figure isn't described by an edge/sign list, so I can't check whether the mini-gadget actually forces this. Without this, Lemma 4 and Theorem 6 don't go through. This is not a minor typo; it's a proof obligation.

The sign error in Theorem 13 is minor: from m ≤ p−3q+21m you get m ≥ (3q−p)/20, not ≤. The paper then continues as if the correct inequality were there, so the intended argument is recoverable. Theorem 16's proof has a notational tangle with a and a_uv, but the inequalities work when you sort out which variable is which.

Bottom line: the central claim is plausible and the construction is likely correct, but the paper as written is not convincing enough for me to cite as a disproof until Lemma 3 is proved in detail. I'd send it to a knowledgeable referee with a request to verify the mini-gadget, and I'd tell the authors to fix the sign error. It deserves peer review.

Referee Report

2 major / 5 minor

Summary. The paper studies fractional balanced colorings of planar signed graphs and fractional arboricity of planar graphs. Its central construction is a planar signed simple graph whose fractional balanced chromatic number is claimed to be strictly larger than 2, which would refute the Bonamy–Kardoš–Kelly–Postle conjecture that every planar graph has fractional arboricity at most 2. The paper further claims, by iterating the construction, that the supremum of the fractional balanced chromatic number over planar signed simple graphs is at least 83/41, and that a specific planar graph W1 has fractional arboricity exactly 2 + 2/25. The arguments rest on a Wenger-type gadget and a 'triangle property' enforcement lemma, together with explicit colorings given in several tables.

Significance. If the main claims are correct, the paper settles a notable open conjecture in the negative and provides the best known lower bounds both for fractional balanced chromatic numbers of planar signed graphs and for fractional arboricity of planar graphs. The paper is constructive: it gives explicit colorings in Tables 1–4, including a (172,85)-coloring and a (52,25)-coloring, and it identifies concrete graphs rather than relying on non-effective arguments. These are genuine strengths. However, the central construction depends on a lemma whose proof is not fully specified, and the derivation of the 83/41 lower bound contains a sign error. Because the main theorem is load-bearing on these points, the paper cannot be accepted in its current form, but the identified issues appear repairable within the scope of the manuscript.

major comments (2)

[§2, Lemma 3 (Figure 1)] The enforcement of the triangle property for positive facial triangles is asserted, not proved. The proof states that 'if a color c appears in all three of the u_i, then it can appear in none of the u′_j which is not possible,' but it does not specify the signs of the edges between the outer triangle u1u2u3 and the inner triangle u′1u′2u′3, nor does it justify why c cannot appear on any u′_j. A complete argument requires that the three triangles u_{j+1}u_{j+2}u′_j (indices mod 3) be negative, so that a color appearing on all three outer vertices and on one inner vertex would form a negative monochromatic triangle. In addition, the inner negative triangle u′1u′2u′3 and the three new facial negative triangles created by the mini-gadget must themselves be given the triangle property by the (K4,−) construction, which is not stated. Since Lemma 4 subsequently uses the triangle property on the positive triangles ux1x2 and vx3x4, this gap is load-bearing for Theorem 6.
[§3, Theorem 13] The derivation of p/q ≥ 83/41 contains a sign error. Corollary 12 gives m_{p,q} ≤ p − 3q + 21m_{p,q}; rearranging yields m_{p,q} ≥ (3q − p)/20, not m_{p,q} ≤ (3q − p)/20 as written. Only after this correction does the combination with m_{p,q} ≤ 2p − 4q (Lemma 10) give p/q ≥ 83/41. The theorem statement is therefore plausible, but the proof as printed is invalid.

minor comments (5)

[§1, Abstract] There is a typo: 'minimum total wight' should be 'weight'.
[§4, proof of Theorem 15] The sentence 'In coloring of Table 2 for every edge the number of common colors on the end points of each edge is 14' should refer to Table 3, not Table 2.
[§4, proof of Theorem 15] In the third base-case tuple for operation [1], the values (a12,a13,a23,a14,a24,a34) = (14,14,14,14,14,13) are inconsistent with the listed third possibility (a12,a13,a23) = (14,13,13) and with the counting identity 2Σa_ij + Σb_i = 4q. Presumably the tuple should be (14,13,13,14,14,13).
[§4, Theorem 14] The list of triangles required to satisfy the triangle property omits wx1x5, which is among the seven triangles enumerated in Remark 5.
[§2, Figure 1] The mini-gadget of Figure 1 would be much easier to verify if the signs of all edges were given explicitly in an adjacency list; the current figure alone is insufficient to support the argument in Lemma 3.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main claims follow from self-contained gadget constructions, counting inequalities, and explicitly listed colorings.

full rationale

The derivation chain is self-contained rather than circular. The central lower bound in Theorem 6 rests on Lemma 4, whose proof is a case analysis on the gadget cW; the lemma assumes only the triangle property, whose enforcement is supplied by Lemma 3 via explicit constructions. In Lemma 3, the negative-triangle part is a counting statement on (K4,-): with 4 vertices, 2k colors, and balanced color classes of size at most 2, each color appears exactly twice. The positive-triangle mini-gadget then uses that already-enforced property on the inner negative triangle; the assertion that a color appearing on all three u_i cannot appear on none of the u'_j is exactly the enforced triangle property, not an assumption of the theorem being proved. Lemma 10 bounds m_{p,q} using (K4,-), and Corollary 12 combines this with the recursive inequality for bG*; this is an inductive use of the definition of m_{p,q}, not an import of the target bound. The (172,85)- and (83,41)-colorings and the (52,25)-coloring of W1 are given explicitly in Tables 1-4, so upper bounds are constructive and not fitted. Self-citations [5] and [7] only introduce the fractional balanced chromatic number terminology; no load-bearing argument reduces to them. The sign-inequality flip in the proof of Theorem 13 and the inconsistent 2+2/25 versus 2+2/31 values are correctness or typographical concerns, not circularity.

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

The paper introduces no fitted parameters and no new physical or mathematical entities. The constructions rest on standard planar embedding, signed graph switching, and combinatorial counting. The gadget structure is the main assumption, and its correctness is addressed through case analyses rather than external benchmarks.

assumptions (3)

standard math Planar graphs admit plane embeddings; faces can be triangulated by adding vertices without destroying planarity or simplicity.
Used in Lemma 3 and Theorem 6 to insert vertices inside facial triangles.
standard math Switching equivalence: flipping signs at vertices preserves the set of balanced sets.
Used throughout for normalizing triangles to all-positive or all-negative.
domain assumption The Wenger-like gadget and its signed completions can be embedded as planar simple signed graphs with the specified facial triangles.
The text refers to Figures 2-4; the actual embeddings are not fully described in words, only drawn.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Fractional balanced chromatic number and arboricity of planar (signed) graphs." pith.science (2026). https://pith.science/paper/HEYGOP2J

@misc{pith2026250516808,
  author       = {Pith},
  title        = {Pith review of: Fractional balanced chromatic number and arboricity of planar (signed) graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HEYGOP2J}},
  note         = {Machine review of arXiv:2505.16808}
}

abstract

A fractional coloring of a signed graph $(G, {\sigma})$ is an assignment of nonnegative weights to the balanced sets (sets which do not induce a negative cycle) such that each vertex has an accumulated weight of at least 1. The minimum total wight among all such colorings is defined to be the fractional balanced chromatic number, denoted by $\chi-{fb}(G, {\sigma})$. This value is clearly upper bounded by the fractional arboricity of $G$, denoted $a_f (G)$, where weights are assigned to sets inducing no cycle rather than sets inducing no negative cycle. In this work we present an example of a planar signed simple graph of fractional balanced chromatic number larger than 2, thus in particular refuting a conjecture of Bonamy, Kardos, Kelly, and Postle suggesting that the fractional arboricity of planar graphs is bounded above by 2. By iterating the construction, we show that the supremum of the fractional balanced chromatic number of planar signed simple graphs is at least as $83/41 = 2 + 1/41$. With similar operations, we built a sequence of planar graphs whose limit of fractional arboricity is $a_f (G) = 2 + 2/25$.

Figures

Figures reproduced from arXiv: 2505.16808 by the authors.

**Figure 1.** Completing the positive triangle Assuming every facial triangle must satisfy the triangle property next we build the key gadget. Lemma 4. In every balanced (2k, k)-coloring of the signed graph Wc of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** The signed graph Wc In case i. A induces negative 5-cycle ux2wx4v and in case ii. A induces negative 5-cycle ux5wx3v. This contradicts the fact that A is a balanced set, thus proving the claim. Remark 5. To prove the lemma 4 we have used the triangle property on the following seven triangles: ux1x2,vx3x4, wx1x2, wx1x5, wx3x4, zx2x3 and tx4x5, where the first two are positive and five others are negative. Theorem 6. … view at source ↗

**Figure 3.** The signed graph Wc′ fractional balanced chromatic number is calculated in the next section to be 2 + 2 85 , similarly, by identifying copies of z, we may reduce the number of vertices to 127. 3 Improving the lower bound A better understanding of what make the gadget and the examples work leads to an improved lower bound. To that end we first consider the gadget Wc′ of [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Signed planar graphs satisfying χfb > 2 with an extension It can be readily verified that adding any vertex except x4 to {u, v, x1, x2} induces a negative cycle. Thus B1 is indeed the only maximal balanced set containing {u, v, x1, x2}. Similarly B2 is the only maximal…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

A conjecture on planar graphs.Graph theory and related topics, 357:357, 1979

Michael O Albertson and David M Berman. A conjecture on planar graphs.Graph theory and related topics, 357:357, 1979. 15

work page 1979
[2]

Fractional vertex- arboricity of planar graphs, 2020

Marthe Bonamy, Frantiˇ sek Kardoˇ s, Tom Kelly, and Luke Postle. Fractional vertex- arboricity of planar graphs, 2020

work page 2020
[3]

O. V. Borodin. A proof of B. Gr¨ unbaum’s conjecture on the acyclic 5-colorability of planar graphs.Dokl. Akad. Nauk SSSR, 231(1):18–20, 1976

work page 1976
[4]

Paul A. Catlin. Haj´ os’ graph-coloring conjecture: variations and counterexamples.J. Combin. Theory Ser. B, 26(2):268–274, 1979

work page 1979
[5]

Balanced-chromatic number and hadwiger-like conjectures.Priprint, 2024+

Andrea Jimenez, Jessica McDonald, Reza Naserasr, Kathryn Nurse, and Daniel Quiroz. Balanced-chromatic number and hadwiger-like conjectures.Priprint, 2024+

work page 2024
[6]

On the 4-color theorem for signed graphs

Frantiˇ sek Kardoˇ s and Jonathan Narboni. On the 4-color theorem for signed graphs. European J. Combin., 91:Paper No. 103215, 8, 2021

work page 2021
[7]

Fractional balanced colouring of signed graphs.Priprint, 2025+

Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, and Xuding Zhu. Fractional balanced colouring of signed graphs.Priprint, 2025+

work page 2025
[8]

The chromatic number of a signed graph.Electron

Edita M´ aˇ cajov´ a, Andr´ e Raspaud, and MartinˇSkoviera. The chromatic number of a signed graph.Electron. J. Combin., 23(1):Paper 1.14, 10, 2016

work page 2016

Show all 13 references

[9]

Complex and homomorphic chromatic number of signed planar simple graphs.Graphs Combin., 38(3):Paper No

Reza Naserasr and Lan Anh Pham. Complex and homomorphic chromatic number of signed planar simple graphs.Graphs Combin., 38(3):Paper No. 58, 22, 2022

2022
[10]

P. G. Tait. Listing‘s topology.Phil. Mag. (5th Ser.), 17:30–46, 1884
[11]

W. T. Tutte. On Hamiltonian circuits.J. London Math. Soc., 21:98–101, 1946

1946
[12]

Note on a paper of B

Gerd Wegner. Note on a paper of B. Gr¨ unbaum on acyclic colorings.Israel J. Math., 14:409–412, 1973

1973
[13]

Balanced decompositions of a signed graph.J

Thomas Zaslavsky. Balanced decompositions of a signed graph.J. Combin. Theory Ser. B, 43(1):1–13, 1987. 16

1987

Pith tools

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

[1] [1]

A conjecture on planar graphs.Graph theory and related topics, 357:357, 1979

Michael O Albertson and David M Berman. A conjecture on planar graphs.Graph theory and related topics, 357:357, 1979. 15

work page 1979

[2] [2]

Fractional vertex- arboricity of planar graphs, 2020

Marthe Bonamy, Frantiˇ sek Kardoˇ s, Tom Kelly, and Luke Postle. Fractional vertex- arboricity of planar graphs, 2020

work page 2020

[3] [3]

O. V. Borodin. A proof of B. Gr¨ unbaum’s conjecture on the acyclic 5-colorability of planar graphs.Dokl. Akad. Nauk SSSR, 231(1):18–20, 1976

work page 1976

[4] [4]

Paul A. Catlin. Haj´ os’ graph-coloring conjecture: variations and counterexamples.J. Combin. Theory Ser. B, 26(2):268–274, 1979

work page 1979

[5] [5]

Balanced-chromatic number and hadwiger-like conjectures.Priprint, 2024+

Andrea Jimenez, Jessica McDonald, Reza Naserasr, Kathryn Nurse, and Daniel Quiroz. Balanced-chromatic number and hadwiger-like conjectures.Priprint, 2024+

work page 2024

[6] [6]

On the 4-color theorem for signed graphs

Frantiˇ sek Kardoˇ s and Jonathan Narboni. On the 4-color theorem for signed graphs. European J. Combin., 91:Paper No. 103215, 8, 2021

work page 2021

[7] [7]

Fractional balanced colouring of signed graphs.Priprint, 2025+

Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou, and Xuding Zhu. Fractional balanced colouring of signed graphs.Priprint, 2025+

work page 2025

[8] [8]

The chromatic number of a signed graph.Electron

Edita M´ aˇ cajov´ a, Andr´ e Raspaud, and MartinˇSkoviera. The chromatic number of a signed graph.Electron. J. Combin., 23(1):Paper 1.14, 10, 2016

work page 2016