Pith. sign in

REVIEW 12 references

The List Edge-Coloring Conjecture for Two New Infinite Families of Complete Graphs

T0 review · reviewed 2026-08-28 · deepseek-v4-flash

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

Pith's one-line read For every odd prime p, the complete graphs K_{p-1} and K_{2p} have list chromatic index equal to their edge-chromatic number, confirming the List Edge-Coloring Conjecture for two new infinite families.

arxiv 2608.22895 v1 pith:ZKSQT2DX submitted 2026-08-24 math.CO

Amir Jafari This is my paper · ORCID
classification math.CO
keywords pfaffiansignsignedcompletecongruenceconjectureedge-coloringfamilies
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

The paper studies the list edge-coloring conjecture, a central question in graph theory. The conjecture says that every graph can have its edges properly colored even when each edge is given its own personalized list of colors, as long as every list is at least as large as the number of colors needed for an ordinary edge coloring. The conjecture is known for many graphs, but for complete graphs with an even number of vertices it has remained open for decades. The author proves the conjecture for two new families of complete graphs: those with p-1 vertices and those with 2p vertices, where p is any odd prime. The proof strategy is to count all ways to split the graph's edges into perfect matchings, called one-factorizations, and to give each factorization a plus or minus sign. If the signed total is nonzero, then a theorem by Alon and Tarsi guarantees that the graph admits the desired edge coloring from arbitrary lists. The two families need different techniques. For K_{p-1}, a known congruence for determinant coefficients is transformed through a Pfaffian calculation into a tiny sum that is easy to evaluate, and the result is nonzero modulo p. For K_{2p}, the author uses a symmetry-based counting argument to isolate the contribution of diagonal shifts, and a matrix identity shows the surviving sum is nonzero modulo p squared. The paper also examines a natural extension and finds a divisibility barrier that prevents the second method from reaching larger families, a limitation the authors openly state.
Extended reading notes

Core claim

For every odd prime p, the List Edge-Coloring Conjecture holds for K_{p-1} and K_{2p}: chi'_l(K_{p-1}) = p-2 and chi'_l(K_{2p}) = 2p-1. More precisely, the paper proves [x^1] Pf(X)^{p-2} is congruent to (-2)^{(p-1)/2} modulo p and S_{2p} is congruent to -p modulo p^2, where S_n is the signed count of unordered one-factorizations, and the nonzero residues trigger the Alon-Tarsi-Ellingham-Goddyn criterion.

Load-bearing premise

Lemma 6.1, the classification of diagonally invariant one-factorizations of K_{2p} into a residue d0, the p-1 fixed matchings M_d with d not equal to d0, and an ordered pair (A,B) of starters. If any invariant factorization were missed by this classification, the equality F_diag = p T_p^2 would fail and the congruence S_{2p} is congruent to -p modulo p^2 would collapse. The classification and its sign computation in Lemma 6.2 are compact and sign-sensitive.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: For every odd prime p, the List Edge-Coloring Conjecture holds for K_{p-1} and K_{2p}: chi'_l(K_{p-1}) = p-2 and chi'_l(K_{2p}) = 2p-1. More precisely, the paper proves [x^1] Pf(X)^{p-2} is congruent to (-2)^{(p-1)/2} modulo p and S_{2p} is congruent to -p modulo p^2, where S_n is the signed count of unordered one-factorizations, and the nonzero residues trigger the Alon-Tarsi-Ellingham-Goddyn cri

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

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

The central claims rest on two external theorems, Glynn's determinant congruence and the Alon-Tarsi-Ellingham-Goddyn polynomial criterion, plus standard algebraic tools. No free parameters are fitted; no new entities are postulated. The special constructs, such as the matching M0 and the skew-circulant matrix C, are proof devices rather than assumptions carrying independent evidence.

assumptions (3)
  • domain assumption Alon-Tarsi-Ellingham-Goddyn criterion: for k-regular one-factorable G, the coefficient [product x_e^{k-1}] P_{L(G)} equals plus or minus k! times the signed one-factorization sum, and nonvanishing of that sum implies chi'_l(G)=k.
    Invoked in Section 2, equations (2.2) and (2.3), citing references [1,4,11]. Both main theorems use it to convert the computed nonzero signed sums into edge-choosability.
  • domain assumption Glynn's coefficient congruence: for any nonnegative integral matrix L with row and column sums p-1, L! C_L is congruent to (-1)^r modulo p, where C_L is the coefficient of Y^L in (det Y)^{p-1}.
    Theorem 3.1, cited to reference [6]. The entire K_{p-1} proof reduces determinant coefficients to 1/L! modulo p through this theorem.
  • standard math Standard algebra and number theory: Wilson's theorem, Fermat's little theorem, Frobenius endomorphism, Pfaffian expansion, cyclic Fourier diagonalization, Mobius inversion, and Burnside's lemma.
    Used throughout Sections 3 to 8 with no special hypotheses beyond the stated odd-prime conditions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The List Edge-Coloring Conjecture for Two New Infinite Families of Complete Graphs." pith.science (2026). https://pith.science/paper/ZKSQT2DX

@misc{pith2026260822895,
  author       = {Pith},
  title        = {Pith review of: The List Edge-Coloring Conjecture for Two New Infinite Families of Complete Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZKSQT2DX}},
  note         = {Machine review of arXiv:2608.22895}
}
abstract

Let $p$ be an odd prime. We prove the List Edge-Coloring Conjecture for two infinite families of complete graphs: \[ \chi'_{\ell}(K_{p-1})=p-2, \qquad \chi'_{\ell}(K_{2p})=2p-1. \] The two proofs control the Pfaffian sign of one-factorizations by complementary modular methods. For $K_{p-1}$, Frobenius and a skew specialization turn Glynn's determinant-coefficient congruence into a squarefree Pfaffian coefficient. A divided difference then reduces the remaining calculation to a single antidiagonal Pfaffian and gives \[[x^{\mathbf{1}}]\mbox{Pf}(X)^{p-2}\equiv(-2)^{(p-1)/2}\pmod{p}.\] For $K_{2p}$, a weighted Burnside count for the translation group $\Bbb{F}_p^2$ isolates a signed cyclic-starter sum. A skew-circulant cofactor identity evaluates its square and gives \[ S_{2p}\equiv-p\pmod{p^2}. \] In particular, both decisive signed sums are nonzero. Neither congruence is a formal consequence of Latin-square parity: the bipartite determinant sign and the nonbipartite Pfaffian sign are different invariants. Instead, the proofs develop a determinant--Pfaffian bridge and a signed Burnside--Fourier method adapted to the complete-graph sign. We also locate a limit of the latter method. For every even $b\ge4$, the signed trace of a full-support translation on $K_{bp}$ is divisible by $p^b$. For $b=4$ this implies $p^4\mid S_{4p}$ but supplies no nonzero residue, revealing a valuation barrier to the full-support higher-layer argument.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Alon and M

    N. Alon and M. Tarsi,Colorings and orientations of graphs, Combinatorica 12 (1992), 125–134. doi:10.1007/BF01204715

    work page doi:10.1007/bf01204715 1992

  2. [2]

    A. A. Drisko,On the number of even and odd Latin squares of orderp + 1, Adv. Math. 128 (1997), 20–35. doi:10.1006/aima.1997.1623

    work page arXiv 1997

  3. [3]

    A. A. Drisko,Proof of the Alon–Tarsi conjecture forn = 2rp, Electron. J. Combin. 5 (1998), Research Paper 28. doi:10.37236/1366. 18

    work page doi:10.37236/1366 1998

  4. [4]

    M. N. Ellingham and L. Goddyn,List edge colourings of some1-factorable multigraphs, Combinatorica 16 (1996), 343–352. doi:10.1007/BF01261320

    work page doi:10.1007/bf01261320 1996

  5. [5]

    Galvin,The list chromatic index of a bipartite multigraph, J

    F. Galvin,The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B 63 (1995), 153–158. doi:10.1006/jctb.1995.1011

    work page arXiv 1995

  6. [6]

    D. G. Glynn,The conjectures of Alon–Tarsi and Rota in dimension prime minus one, SIAM J. Discrete Math. 24 (2010), 394–399. doi:10.1137/090773751

    work page doi:10.1137/090773751 2010

  7. [7]

    Häggkvist and J

    R. Häggkvist and J. C. M. Janssen,New bounds on the list-chromatic index of the complete graph and other simple graphs, Combin. Probab. Comput. 6 (1997), 295–313. doi:10.1017/S0963548397002927

    work page doi:10.1017/s0963548397002927 1997

  8. [8]

    Itoh and J

    M. Itoh and J. Shimoyoshi,A condition for the existence of zero coefficients in the powers of the determinant polynomial, J. Algebra 579 (2021), 231–236. doi:10.1016/j.jalgebra.2021.03.017

    work page doi:10.1016/j.jalgebra.2021.03.017 2021

Show all 12 references
  1. [9]

    Rabern,The list-chromatic index ofK8 andK 10, unpublished note, 2014

    L. Rabern,The list-chromatic index ofK8 andK 10, unpublished note, 2014. Available online

    2014

  2. [10]

    Schauz,Proof of the List Edge Coloring Conjecture for complete graphs of prime degree, Electron

    U. Schauz,Proof of the List Edge Coloring Conjecture for complete graphs of prime degree, Electron. J. Combin. 21(3) (2014), Paper P3.43. doi:10.37236/4084

    2014 doi

  3. [11]

    Schauz,Computing the list chromatic index of graphs, J

    U. Schauz,Computing the list chromatic index of graphs, J. Discrete Algorithms 52–53 (2018), 182–191. doi:10.1016/j.jda.2018.11.014

    2018 doi

  4. [12]

    Zappa,The Cayley determinant of the determinant tensor and the Alon–Tarsi conjecture, Adv

    P. Zappa,The Cayley determinant of the determinant tensor and the Alon–Tarsi conjecture, Adv. Appl. Math. 19 (1997), 31–44. doi:10.1006/aama.1996.0522. 19

    1997

Pith tools

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