Pith. sign in

REVIEW 3 major objections 4 minor 17 references

Strong parity edge-colorings of graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Every strong parity edge-coloring of a connected graph is a refinement of a coloring generated by an injective binary labeling, and this characterization yields exact values and answers open questions.

desk verdict Strong algebraic characterization, but the bipartite lower bound rests on a false inequality and needs fixing. read the letter →

arxiv 2411.11124 v1 pith:W2BZSPF5 submitted 2024-11-17 math.CO

Peter Bradshaw , Sergey Norin , Douglas B. West This is my paper · ORCID
classification math.CO MSC 05C15
keywords strongparityedge-coloringcanonicalbinarylabelingHopf-Stiefelfunctionhypercubeembeddingspathpowersbipartitegraphs
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

Strong parity edge-colorings forbid open walks in which every color appears an even number of times. This paper proves that all such colorings of connected graphs have one rigid shape: they are exactly the colorings obtained by splitting the color classes of a canonical edge-coloring, where the color of an edge is the binary sum of an injective labeling of its endpoints. With that characterization in hand, the minimum number of colors becomes an optimization over binary labelings, and the paper uses it to settle exact values and open questions that previously resisted direct coloring arguments. The payoff includes the conjectured value for complete bipartite graphs, a hypercube characterization of graphs with smallest possible strong parity number, near-tight bounds for powers of paths, and bipartite graphs where the strong parity number exceeds the parity number by an arbitrarily large factor.

What carries the argument

The load-bearing construction is the family of walk-sum sets $S_v$: for a fixed root $r$, each $S_v$ collects the binary sums (symmetric differences of color sets) of all walks from $r$ to $v$. Lemma 2.4 shows a coloring is strong exactly when these sets are pairwise disjoint; Lemma 2.5 shows they are cosets of the subspace $S_r$ of closed-walk sums; Lemma 2.6 shows the cosets form a binary vector space. The edge $uv$ is then assigned the coset $S_u+S_v$, producing the canonical coloring that refines the original one. The atomic encoding of colors as unit vectors in $\mathbb{F}_2^\infty$ is what makes these sums meaningful. This mechanism is what converts a coloring problem into a linear algebra problem and drives every application.

What would settle it

Compute $p(G_k)$ exactly for small $k$ in Construction 5.4 by exhaustive search. If $p(G_k)$ exceeds $2k+k^{1/3}$ for some $k$, the cut-vertex reuse step fails and the claimed unbounded ratio is not established; a direct display of a parity path in the reused branch coloring would also refute it.

Watch

Extended reading notes

Core claim

The paper's central theorem is that every strong parity edge-coloring $\phi$ of a connected graph is isomorphic to a refinement of a canonical edge-coloring. A canonical edge-coloring is generated by an injective binary labeling $f$ that assigns each vertex a vector over $\mathbb{F}_2$; the color of edge $uv$ is $f(u)+f(v)$. Because splitting color classes of a strong parity coloring preserves the property, every canonical coloring is automatically strong; Theorem 1.5 supplies the converse. Consequently $\hat{p}(G)$, the minimum number of colors in a strong parity edge-coloring, equals the minimum number of colors in any canonical edge-coloring of $G$, reducing the problem to an injective labeling problem. The theorem is proved by encoding colors as unit vectors, fixing a root, and collecting for each vertex $v$ the set $S_v$ of binary sums of colors along all walks from the root to $v$; for a strong parity coloring these sets are pairwise disjoint cosets that themselves form a binary vector space, and the map sending edge $uv$ to the coset $S_u+S_v$ is exactly the required canonical coloring.

Load-bearing premise

For the bipartite ratio application, the argument assumes that joining several components at a single vertex behaves like joining them by an edge: the reused color sets in the components together with one fresh color for the attachment edges never create a parity path, so the upper bound on $p(G_k)$ holds.

Editorial extensions

If this is right

  • The strong parity chromatic number of $K_{s,t}$ is the Hopf–Stiefel function $s\circ t$, resolving the conjecture from the papers that introduced these parameters; in particular $\hat{p}(K_{n,n})$ is the least power of $2$ at least $n$.
  • A connected $n$-vertex graph satisfies $\hat{p}(G)=\lceil \log_2 n\rceil$ exactly when it is a subgraph of the hypercube $Q_{\lceil \log_2 n\rceil}$, answering the equality question posed in [3].
  • For the $\ell$th power of an $n$-vertex path, $\hat{p}(P_n^\ell)$ lies between $\ell\lceil \log_2 n\rceil-\binom{\ell+1}{2}$ and $\ell\lceil \log_2 n\rceil-\ell(\lfloor \lg \ell\rfloor-1)$, so the bounds agree to $O(\ell^2)$ and are asymptotically $\ell\lceil \log_2 n\rceil$ for fixed $\ell$.
  • There exist bipartite graphs with $\hat{p}(G)/p(G)$ arbitrarily large; for each $k$ there is a bipartite $G_k$ with $p(G_k)\le 2k+k^{1/3}$ and $\hat{p}(G_k)\ge(\frac13-o(1))k\ln k$, disproving the conjecture that the two parameters agree on bipartite graphs.
  • Because every strong parity edge-coloring is a refinement of a canonical coloring, finding an optimal strong coloring is equivalent to finding an injective binary labeling that minimizes the number of distinct edge-difference vectors, so future lower bounds can be phrased in this algebraic language.

Reading between the lines

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

  • If the characterization is correct, computing $\hat{p}(G)$ for small graphs can be reduced to a search over injective binary labelings rather than over colorings; an exhaustive check on graphs up to eight vertices would be a quick way to test the theorem and to tabulate the parameter.
  • The bipartite counterexample points to cut structure as the engine of the gap between $p$ and $\hat{p}$. A natural next question, not addressed in the paper, is whether bounded-degree bipartite graphs can already force an unbounded ratio; the construction here uses vertices of degree growing with $k$.
  • The Gray-code coloring of path powers is conjectured optimal. If true, exact values for $\hat{p}(P_n^\ell)$ with small fixed $\ell$ would follow, and the conjecture could be checked by computing the walk-sum lower bound on small instances.
  • The sumset argument for $K_{s,t}$ suggests a coding-theoretic reading: a canonical coloring with $k$ colors is a map from vertices to $\mathbb{F}_2^k$ whose edge-difference set is small, so optimizing $\hat{p}$ is a finite-dimensional difference-set minimization that may support algorithmic or probabilistic bounds not explored here.
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.

Referee Report

3 major / 4 minor

Summary. The paper develops an algebraic characterization of strong parity edge-colorings: it defines a binary-vector-space analogue of edge colors and shows (Theorem 1.5 / Theorem 2.7) that every strong parity edge-coloring of a connected graph is a refinement of a canonical edge-coloring arising from an injective binary vertex labeling. This reduces the strong parity edge-chromatic number to a canonical labeling problem. The paper then uses this characterization to prove that \hat p(K_{s,t}) equals the Hopf–Stiefel function s∘t, to characterize connected graphs with \hat p(G)=⌈lg n⌉ as subgraphs of the hypercube, to give nearly tight bounds for powers of paths, and to construct bipartite graphs with \hat p(G)/p(G) arbitrarily large. The first three applications are derived cleanly from the algebraic framework and external results. The bipartite construction, however, contains a serious gap in the proof of the advertised lower bound.

Significance. The algebraic framework in Section 2 is elegant and appears correct; Theorem 2.7 is a genuine structural result that unifies earlier work of Bunde, Milans, West, and Wu and yields the Hopf–Stiefel formula and the hypercube characterization as short corollaries. These contributions alone make the paper valuable. The paper also makes good use of external theorems (Yuzvinsky's sumset theorem, the Havel–Morávek hypercube characterization) without circularity. However, the proof of the lower bound for the bipartite ratio construction contains a false inequality, so the advertised Theorem 1.14 is not established as written. The paper should not be accepted in its current form.

major comments (3)
  1. [Section 5, Theorem 5.5] The proof of the lower bound asserts the chain |T∩X_d| ≥ lg|Y_d| − (r−d+1)(2d−2) ≥ ⌈k/d⌉ − (r−d+1)(2d−2). The second inequality is false. Saturating only gives |T∩Y_d| ≥ lg(1+|Y_d|), which is O(log k) because |Y_d| is a sum of terms 2⌈k/ℓ⌉ and is at most 2k(1+ln r). For example, if k=64, r=4, and d=4, then |Y_4|=32 and lg|Y_4|=5, but ⌈k/d⌉=16. Thus the bound |T∩X_d| ≥ ⌈k/d⌉−2rd is unsupported, and the subsequent sum ∑_{d=1}^r |T∩X_d| ≥ (1/3−o(1))k ln k does not follow. Since this is the only argument for the lower bound in Theorem 1.14, the claim that \hat p(G_k)/p(G_k) is unbounded for bipartite graphs is not proved.
  2. [Section 5, Theorem 5.2] The proof cites “Proposition 1.3” when deriving p(G)=n+1, but no Proposition 1.3 appears in the manuscript. The equality p(G)=n+1 is load-bearing for the disproof of Conjecture 1.12, because the subsequent lower bound on \hat p(G) is compared to this value. Please supply the correct reference or a proof of the needed bound on p(K_{n,n}) (or on the relevant component).
  3. [Section 5, Construction 5.4] Lemma 5.1 is stated only for a graph with one cut-edge, but G_k is formed by identifying a vertex u across r blocks, leaving r cut-edges incident to u. The sentence “Lemma 5.1 now yields p(G_k) < 2k + k^{1/3}” skips the necessary induction over these r cut-edges. The bound is plausible and can be obtained by iterating Lemma 5.1 while giving a distinct fresh color to each new cut-edge, but the manuscript should state this explicitly because the proof as written does not formally cover the multi-cut-edge setting.
minor comments (4)
  1. [Section 2 and Section 3] Theorem 1.3 is stated and proved twice: once after Example 2.8 using Theorem 1.5 and again in Section 3 using Lemma 3.1. One of the two proofs should be removed or the duplication should be noted.
  2. [Section 5, Remark 5.3] Remark 5.3 claims stronger bounds 2n−(2+o(1))√n ≤ \hat p(G) ≤ 2n−lg n+1 for the graph of Theorem 5.2 and says the details are omitted. As written these are unproved assertions; they should be labeled as conjectural or a proof should be supplied, especially since the wording suggests they follow from the earlier tools.
  3. [Section 5, Theorem 5.5 proof] The statement that X_d consists of Y_d except for 2d−2 vertices at the beginning of each Z_ℓ appears off by one: for d=1, the first vertex of each Z_ℓ has back-degree 0, so one vertex is excluded per block, not zero. The subtraction term should be adjusted consistently.
  4. [Throughout] There are several typographical errors: “establishs” in Section 4, “color clases” in the proof of Theorem 2.7, and a formatting artifact “Ha/suppress luszczak” in reference [1]. These should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central characterization is proved from definitions, and applications rely on external theorems or internal lemmas.

full rationale

The paper's central claim, Theorem 1.5, is not circular. It is proved in Section 2 from the definitions of spec and canonical edge-coloring: the sets S_v are shown to be disjoint cosets of a subspace (Lemmas 2.4 and 2.5), the cosets are shown to form a binary vector space (Lemma 2.6), and Theorem 2.7 constructs the canonical coloring phi* = pi ∘ phi, using no more colors than phi. This is a genuine reduction, not a restatement of the target. The applications are likewise driven by independent ingredients: Theorem 1.9 uses Yuzvinsky's sumset theorem (Theorem 1.8), Theorem 1.3 uses the external Havel-Moravek characterization, and the path-power bounds use the internal Gray-code construction together with Lemma 3.3 and Corollary 3.4. The self-citations to Bunde-Milans-West-Wu are for background definitions, conjectures, and elementary baseline bounds such as p(G) >= lg n; none of these is load-bearing for the main characterization, since the paper proves the stronger Lemma 3.1 itself. Any suspected issues in Section 5, such as the application of Lemma 5.1 through a cut vertex or the numerical bound |T ∩ X_d| >= ceil(k/d), are correctness concerns about the proof as written, not instances of fitting an input and calling it a prediction or importing a conclusion through a self-citation.

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

No numerical constants are fitted and no new physical or mathematical entities are postulated. The paper's burden is carried by standard linear algebra plus several quoted external theorems from additive combinatorics and hypercube theory.

assumptions (5)
  • standard math Linear algebra over F2: edge subsets form a vector space; cosets of a subspace form a quotient vector space.
    Used throughout Section 2 to define atomic edge-colorings, S_v sets, and the canonical quotient coloring in Theorem 2.7.
  • domain assumption Yuzvinsky's theorem: for |A| = s and |B| = t, |A+B| >= s o t with equality attainable.
    Invoked in Section 1 to identify the minimum number of colors in a canonical coloring of K_{s,t} with the Hopf-Stiefel value s o t.
  • domain assumption Havel-Moravek characterization: a connected graph embeds in Q_k iff it has a parity edge-coloring with at most k colors in which every cycle is a parity walk.
    Used in the second proof of Theorem 1.3 to convert the equality condition into a subgraph-of-hypercube condition.
  • domain assumption Plagne and Karolyi formula for the Hopf-Stiefel function s o t.
    Quoted in the introduction to express s o t in closed form and to state the K_{s,t} result.
  • domain assumption Known values p(P_n) = phat(P_n) = ceil(log2 n) and p(C_n) values from Bunde et al.
    Used for context and for the exact ℓ = 1 case in Theorem 4.1; these are external results from the authors' earlier work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong parity edge-colorings of graphs." pith.science (2026). https://pith.science/paper/W2BZSPF5

@misc{pith2026241111124,
  author       = {Pith},
  title        = {Pith review of: Strong parity edge-colorings of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W2BZSPF5}},
  note         = {Machine review of arXiv:2411.11124}
}
abstract

An edge-coloring of a graph $G$ assigns a color to each edge of $G$. An edge-coloring is a parity edge-coloring if for each path $P$ in $G$, it uses some color on an odd number of edges in $P$. It is a strong parity edge-coloring if for every open walk $W$ in $G$, it uses some color an odd number of times along $W$. The minimum numbers of colors in parity and strong parity edge-colorings of $G$ are denoted $p(G)$ and $\hat{p}(G)$, respectively. We characterize strong parity edge-colorings and use this characterization to prove lower bounds on $\hat{p}(G)$ and answer several questions of Bunde, Milans, West, and Wu. The applications are as follows. (1) We prove the conjecture that $\hat{p}(K_{s,t})=s \circ t$, where $s \circ t$ is the Hopf-Stiefel function. (2) We show that $\hat{p}(G)$ for a connected $n$-vertex graph $G$ equals the known lower bound $\lceil \log_2 n \rceil$ if and only if $G$ is a subgraph of the hypercube $Q_{\lceil \log_2 n \rceil }$. (3) We asymptotically compute $\hat{p}(G)$ when $G$ is the $\ell$th distance-power of a path, proving $\hat{p}(P_n^\ell)\sim\ell \lceil {\log_2 n} \rceil$. (4) We disprove the conjecture that $\hat{p}(G)=p(G)$ when $G$ is bipartite by constructing bipartite graphs $G$ such that $\hat{p}(G)/p(G)$ is arbitrarily large; in particular, with $\hat{p}(G)\ge\frac{1-o(1)}3 k\ln k$ and $p(G)\le2k+k^{1/3}$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    N. Alon, J. Grytczuk, M. Ha/suppress luszczak, and O. Riordan, Nonrepetitive colorings of graphs. Random Structures Algorithms 21 (2002), 336–346

    work page 2002

  2. [2]

    Bollob´ as,The art of mathematics

    B. Bollob´ as,The art of mathematics. Coffee time in Memphis. (Cambridge University Press, New York, 2006), page 186

    work page 2006

  3. [3]

    D. P. Bunde, K. Milans, D. B. West, and H. Wu, Parity and str ong parity edge-coloring of graphs. In Proc. 38th SE Intl. Conf. Comb., Graph Th., Comput. . Congressus Numer. 187 (2007), 193–213

    work page 2007

  4. [4]

    D. P. Bunde, K. Milans, D. B. West, and H. Wu, Optimal stron g parity edge-coloring of complete graphs. Combinatorica 28 (2008), 625–632

    work page 2008

  5. [5]

    Eliahou and M

    S. Eliahou and M. Kervaire, Old and new formulas for the Ho pf-Stiefel and related functions. Expo. Math. 23 (2005), 127–145

    work page 2005

  6. [6]

    E. N. Gilbert, Gray codes and paths on the n-cube. Bell System Tech. J. 37 (1958), 815–826

    work page 1958

  7. [7]

    Havel and J

    I. Havel and J. Mor´ avek,B-valuation of graphs. Czech. Math. J. 22 (1972), 338–351

    work page 1972

  8. [8]

    Hopf, Ein topologischer Beitrag zur reelen Algebra

    H. Hopf, Ein topologischer Beitrag zur reelen Algebra. Comment. Math. Helv. 13 (1940/41), 219–239

    work page 1940

Show all 17 references
  1. [9]

    Hsu and G

    H.-C. Hsu and G. J. Chang, Parity and strong parity edge-c olorings of graphs. J. Comb. Optim. 24 (2012), 427–436. 17

    2012

  2. [10]

    K´ arolyi, A note on the Hopf–Stiefel function

    G. K´ arolyi, A note on the Hopf–Stiefel function. Europ. J. Combin. 27 (2006), 1135–1137

    2006

  3. [11]

    Keevash and B

    P. Keevash and B. Sudakov, On a hypergraph Tur´ an proble m of Frankl. Combinatorica 25 (2005), 673–706

    2005

  4. [12]

    Plagne, Additive number theory sheds extra light on t he Hopf–Stiefel ◦ function

    A. Plagne, Additive number theory sheds extra light on t he Hopf–Stiefel ◦ function. L’Enseignement Math. 49 (2003), 109–116

    2003

  5. [13]

    E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms: Theory and Practice , (Prentice-Hall, 1977), 173–179

    1977

  6. [14]

    Rosenfeld, Another approach to non-repetitive colo rings of graphs of bounded degree

    M. Rosenfeld, Another approach to non-repetitive colo rings of graphs of bounded degree. Electron. J. Combin. 27 (2020), Paper #3.43, 16 pages

    2020

  7. [15]

    Stiefel, ¨Uber Richtungsfelder in den projektiven R¨ aumen und einen S atz aus der reelen Algebra

    E. Stiefel, ¨Uber Richtungsfelder in den projektiven R¨ aumen und einen S atz aus der reelen Algebra. Comment. Math. Helv. 13 (1940/41), 201–218

    1940

  8. [16]

    Thue, ¨Uber unendliche Zeichenreihen

    A. Thue, ¨Uber unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania 7 (1906), 1–22

    1906

  9. [17]

    Yuzvinsky, Orthogonal pairings of Euclidean spaces

    S. Yuzvinsky, Orthogonal pairings of Euclidean spaces . Michigan Math. J. 28 (1981), 131–145. 18

    1981

Pith tools

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