pith. sign in

arxiv: 2605.22860 · v1 · pith:MVBGDGCLnew · submitted 2026-05-19 · 🧮 math.CO

Every signed planar graph is 5-choosable: A short proof and refinements

Pie Desire Ebode Atangana , Maxwell Ndognkon Manga This is my paper

Pith reviewed 2026-05-25 06:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords signed graphsplanar graphslist coloringchoosabilityThomassen theoremsigned coloringouterplanar graphsdefective coloring
0
0 comments X

The pith

Every signed planar graph is 5-choosable.

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

The paper proves that the signed choice number of any planar signed graph is at most 5. It supplies a short inductive argument obtained by inserting a uniform factor of the edge signature into each coloring constraint of Thomassen's original proof for unsigned planar graphs. The same text therefore covers both the signed and unsigned cases, and the strengthened inductive statement immediately yields several further results on outerplanar graphs, defective colorings, and algorithmic consequences. The bound cannot be lowered because the known planar graphs that are not 4-choosable remain non-4-choosable when all edges receive positive sign.

Core claim

Every planar signed graph Gs is signed 5-choosable: from any assignment of lists of size 5 there exists a map c from vertices to integers such that c(u) ≠ σ(uv) c(v) for every edge uv. The argument proceeds by induction on a strengthened extension statement that precolors a boundary cycle while maintaining the same list-size and distance conditions as Thomassen's theorem; the signature enters solely through multiplication by σ in each forbidden-difference constraint. When σ is constantly +1 the proof reduces verbatim to the unsigned case.

What carries the argument

The strengthened extension statement, an inductive claim that inserts one uniform factor of σ into every coloring constraint while preserving the original list sizes and boundary-distance hypotheses.

If this is right

  • chs(Gs) ≤ 5 holds for every planar signed graph Gs.
  • The signed five-color theorem holds in the symmetric palette {-2,-1,0,1,2}.
  • Every outerplanar signed graph is 3-choosable.
  • Every planar signed graph is 1-defective signed 4-choosable.
  • A sandwich inequality relates the signed choice number to the ordinary and positive choice numbers, and list coloring can be performed in polynomial time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The uniform-insertion technique may extend to other inductive coloring arguments originally stated only for unsigned graphs.
  • Switching invariance of signed colorings follows immediately once the proof is written in signature-blind form.
  • The examples in the paper indicate that negative edges can produce coloring obstructions that cannot be reduced to the all-positive case.

Load-bearing premise

The inductive bookkeeping step remains valid after uniformly inserting one factor of σ into every coloring constraint.

What would settle it

An explicit planar signed graph together with lists of size 5 from which no proper signed coloring exists, or a direct counterexample to the strengthened extension statement on some precolored boundary.

read the original abstract

A \emph{signed graph} is a pair $\Gs$ in which $G$ is a finite simple graph and $\sigma:\E(G)\to\{+1,-1\}$ is a \emph{signature}. Following M\'a\v{c}ajov\'a--Raspaud- \v{S}koviera and Jin--Kang--Steffen, a \emph{proper coloring} of $\Gs$ is a map $c:\V(G)\to\Z$ with $c(u)\ne\sigma(uv)\,c(v)$ for every edge $uv$, and $\Gs$ is \emph{signed $k$-choosable} if such a coloring exists from any list assignment $L$ with $|L(v)|\ge k$. In a celebrated two-page note, Thomassen proved that every planar graph is $5$ choosable, and Jin, Kang, and Steffen subsequently extended this to signed planar graphs. Our principal contribution is a short, self-contained, and \emph{signature-blind} proof of the latter: the inductive bookkeeping inserts one factor of $\sigma(\cdot)$ uniformly into every constraint, so that with $\sigma\equiv +1$ the argument reduces verbatim to Thomassen's original. From the strengthened extension statement (\cref{thm:main}) we deduce the main result (\cref{thm:JKS}: $\chs\Gs\le 5$ for every planar signed graph), the M\'a\v{c}ajov\'a--Raspaud--\v{S}koviera signed Five-Color Theorem in the symmetric palette $\Ns{2}=\{-2,-1,0,1,2\}$, the Switching Invariance Lemma, $3$-choosability of outerplanar signed graphs, $1$-defective signed $4$-choosability of planar signed graphs, a sandwich inequality relating $\chs$ to the unsigned and positive'' choice numbers, and a polynomial-time list-coloring algorithm. Voigt's planar non-$4$-choosable graph and Mirzakhani's smaller variant show the bound $5$ is best possible. We close with examples illustrating that negative edges genuinely refine unsigned phenomena, a comparison table situating our work in the literature, and several open problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents a short, self-contained, signature-blind proof that every signed planar graph Gs is 5-choosable. The central argument strengthens Thomassen's inductive extension lemma by uniformly inserting a factor of the signature σ into each coloring constraint (thm:main); the case σ ≡ +1 recovers Thomassen's original proof verbatim. From thm:main the authors deduce the main result (thm:JKS: chs(Gs) ≤ 5), the Máčajová–Raspaud–Škoviera signed five-color theorem in the symmetric palette N2 = {-2,-1,0,1,2}, the switching-invariance lemma, 3-choosability of outerplanar signed graphs, 1-defective signed 4-choosability of planar signed graphs, a sandwich inequality relating chs to the unsigned and positive choice numbers, and a polynomial-time list-coloring algorithm. Tightness follows from Voigt's and Mirzakhani's examples.

Significance. The uniform, signature-blind adaptation supplies a streamlined alternative to the earlier Jin–Kang–Steffen proof while recovering the classical Thomassen theorem as a special case. The additional corollaries (outerplanar 3-choosability, defective choosability, algorithmic consequence) and the explicit comparison table increase the paper's utility. The approach avoids ad-hoc case distinctions on negative edges and is therefore of broader methodological interest.

minor comments (2)
  1. [Abstract] Abstract: the long list of corollaries could be condensed or moved to the introduction to improve readability while preserving the claim that all follow from thm:main.
  2. Ensure every cross-reference (e.g., thm:main, thm:JKS, cref statements) appears with consistent numbering and that the comparison table is explicitly located in the text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation to accept. We are pleased that the signature-blind inductive approach, its recovery of Thomassen's theorem, and the listed corollaries were viewed favorably.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation consists of a uniform modification of Thomassen's external inductive argument by inserting a single factor of σ(·) into each coloring constraint. The paper explicitly states that the σ≡+1 case recovers Thomassen verbatim, and the strengthened extension (thm:main) is used only to deduce the target theorem (thm:JKS) and corollaries. No self-citations are load-bearing for the central claim, no parameters are fitted and renamed as predictions, and no definitions or uniqueness statements loop back to the target result. The argument is self-contained against the external Thomassen benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new free parameters or invented entities. It relies on the standard background that planar graphs admit inductive colorings and on Thomassen's unsigned theorem as the base case.

axioms (1)
  • domain assumption Thomassen's theorem: every planar graph is 5-choosable
    The new argument is stated to reduce directly to this result when σ ≡ +1.

pith-pipeline@v0.9.0 · 5953 in / 1130 out tokens · 58141 ms · 2026-05-25T06:07:55.887797+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages

  1. [1]

    M. O. Albertson,You can’t paint yourself into a corner, J. Combin. Theory Ser. B73 (1998), 189–194

    work page 1998

  2. [2]

    Alon and M

    N. Alon and M. Tarsi,Colorings and orientations of graphs, Combinatorica12(1992), no. 2, 125–134

    work page 1992

  3. [3]

    Appel and W

    K. Appel and W. Haken,Every planar map is four colorable, Illinois J. Math.21(1977), 429–567

    work page 1977

  4. [4]

    Böhme, B

    T. Böhme, B. Mohar, and M. Stiebitz,Dirac’s map-color theorem for choosability, J. Graph Theory32(1999), no. 4, 327–339

    work page 1999

  5. [5]

    J. A. Bondy and U. S. R. Murty,Graph Theory, Graduate Texts in Mathematics 244, Springer, 2008

    work page 2008

  6. [6]

    Bouchet,Nowhere-zero integral flows on a bidirected graph, J

    A. Bouchet,Nowhere-zero integral flows on a bidirected graph, J. Combin. Theory Ser. B 34(1983), 279–292

    work page 1983

  7. [7]

    Chartrand and D

    G. Chartrand and D. P. Geller,On uniquely colorable planar graphs, J. Combin. Theory6 (1969), 271–278

    work page 1969

  8. [8]

    Choi and Z.-X

    S.-J. Choi and Z.-X. Song,Variants of5-choosability of planar graphs, J. Graph Theory86 (2017), 1–16

    work page 2017

  9. [9]

    Choi and H

    I. Choi and H. A. Kierstead,Choosability of graphs on surfaces, Discrete Math.342(2019), 2620–2632

    work page 2019

  10. [10]

    DeVos, K

    M. DeVos, K. Kawarabayashi, and B. Mohar,Locally planar graphs are5-choosable, J. Combin. Theory Ser. B98(2008), 1215–1232

    work page 2008

  11. [11]

    Diestel,Graph Theory(5th ed.), Graduate Texts in Mathematics 173, Springer, 2017

    R. Diestel,Graph Theory(5th ed.), Graduate Texts in Mathematics 173, Springer, 2017

    work page 2017

  12. [12]

    G. A. Dirac,A property of4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc.27(1952), 85–92. 14

    work page 1952

  13. [13]

    Dvořák and L

    Z. Dvořák and L. Postle,Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B129(2018), 38–54

    work page 2018

  14. [14]

    Eaton and T

    N. Eaton and T. Hull,Defective list colorings of planar graphs, Bull. Inst. Combin. Appl. 25(1999), 79–87

    work page 1999

  15. [15]

    Erdős, A

    P. Erdős, A. L. Rubin, and H. Taylor,Choosability in graphs, in: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Arcata, CA, 1979, Congr. Numer.26 (1980), 125–157

    work page 1979

  16. [16]

    Harary,On the notion of balance of a signed graph, Michigan Math

    F. Harary,On the notion of balance of a signed graph, Michigan Math. J.2(1953), 143–146

    work page 1953

  17. [17]

    P. J. Heawood,Map-colour theorem, Quart. J. Pure Appl. Math.24(1890), 332–338

    work page

  18. [18]

    J. E. Hopcroft and R. E. Tarjan,Efficient planarity testing, J. ACM21(1974), 549–568

    work page 1974

  19. [19]

    T. R. Jensen and B. Toft,Graph Coloring Problems, Wiley-Interscience, 1995

    work page 1995

  20. [20]

    L. Jin, Y. Kang, and E. Steffen,Choosability in signed planar graphs, European J. Combin. 52(2016), 234–243

    work page 2016

  21. [21]

    L. Jin, Y. Kang, and E. Steffen,Signed DP-coloring and choosability of signed graphs, preprint (2018)

    work page 2018

  22. [22]

    Kang and E

    Y. Kang and E. Steffen,The chromatic spectrum of signed graphs, Discrete Math.339 (2016), 2660–2663

    work page 2016

  23. [23]

    Kardˇ os and J

    F. Kardˇ os and J. Narboni,On the4-color theorem for signed graphs, European J. Combin. 91(2021), Article 103215, 6 pp

    work page 2021

  24. [24]

    Kratochvíl, Z

    J. Kratochvíl, Z. Tuza, and M. Voigt,New trends in the theory of graph colorings: choosabil- ity and list coloring, in: Contemporary Trends in Discrete Math., DIMACS Ser.49(1999), 183–197

    work page 1999

  25. [25]

    P. C. B. Lam, W. C. Shiu, and B. Xu,On structure of some plane graphs with application to choosability, J. Combin. Theory Ser. B82(2001), 285–296

    work page 2001

  26. [26]

    P. C. B. Lam, B. Xu, and J. Liu,The4-choosability of plane graphs without4-cycles, J. Combin. Theory Ser. B76(1999), 117–126

    work page 1999

  27. [27]

    Lu and J

    H. Lu and J. Ma,Group choosability of signed planar graphs, Discrete Math.342(2019), 1839–1852

    work page 2019

  28. [28]

    Máčajová, A

    E. Máčajová, A. Raspaud, and M. Škoviera,The chromatic number of a signed graph, Electron. J. Combin.23(2016), Paper 1.14, 10 pp

    work page 2016

  29. [29]

    Mirzakhani,A small non-4-choosable planar graph, Bull

    M. Mirzakhani,A small non-4-choosable planar graph, Bull. Inst. Combin. Appl.17(1996), 15–18

    work page 1996

  30. [30]

    Naserasr, E

    R. Naserasr, E. Rollová, and É. Sopena,Homomorphisms of signed graphs, J. Graph Theory 79(2015), 178–212

    work page 2015

  31. [31]

    Naserasr, É

    R. Naserasr, É. Sopena, and T. Zaslavsky,Homomorphisms of signed graphs: an update, European J. Combin.91(2021), 103222

    work page 2021

  32. [32]

    Naserasr, Z

    R. Naserasr, Z. Wang, and X. Zhu,Circular chromatic number of signed graphs, Electron. J. Combin.28(2021), Paper 2.44, 28 pp. 15

    work page 2021

  33. [33]

    Robertson, D

    N. Robertson, D. P. Sanders, P. Seymour, and R. Thomas,The four-colour theorem, J. Combin. Theory Ser. B70(1997), 2–44

    work page 1997

  34. [34]

    Schauz,Mr

    U. Schauz,Mr. Paint and Mrs. Correct, Electron. J. Combin.16(2009), Research Paper 77, 18 pp

    work page 2009

  35. [35]

    Schweser and M

    T. Schweser and M. Stiebitz,Degree choosable signed graphs, Discrete Math.340(2017), 882–891

    work page 2017

  36. [36]

    Schweser, M

    T. Schweser, M. Stiebitz, and B. Toft,Coloring of signed graphs a survey, Discrete Math. 344(2021), Article 112577, 17 pp

    work page 2021

  37. [37]

    Škrekovski,A theorem on map colorings, Bull

    R. Škrekovski,A theorem on map colorings, Bull. Inst. Combin. Appl.23(1998), 65–71

    work page 1998

  38. [38]

    Škrekovski,A Grötzsch-type theorem for list colourings with impropriety one, Combin

    R. Škrekovski,A Grötzsch-type theorem for list colourings with impropriety one, Combin. Probab. Comput.8(1999), 493–507

    work page 1999

  39. [39]

    Škrekovski,List improper colourings of planar graphs with prescribed girth, Discrete Math.214(2000), 221–233

    R. Škrekovski,List improper colourings of planar graphs with prescribed girth, Discrete Math.214(2000), 221–233

    work page 2000

  40. [40]

    Steffen,The chromatic spectrum and the flow spectrum of signed graphs, Discrete Math

    E. Steffen,The chromatic spectrum and the flow spectrum of signed graphs, Discrete Math. 317(2014), 21–29

    work page 2014

  41. [41]

    Thomassen,Every planar graph is5-choosable, J

    C. Thomassen,Every planar graph is5-choosable, J. Combin. Theory Ser. B62(1994), 180–181

    work page 1994

  42. [42]

    Thomassen,3-list-coloring planar graphs of girth5, J

    C. Thomassen,3-list-coloring planar graphs of girth5, J. Combin. Theory Ser. B64(1995), 101–107

    work page 1995

  43. [43]

    Tuza,Graph colorings with local constraints a survey, Discuss

    Zs. Tuza,Graph colorings with local constraints a survey, Discuss. Math. Graph Theory17 (1997), 161–228

    work page 1997

  44. [44]

    V. G. Vizing,Coloring the vertices of a graph in prescribed colors(in Russian), Diskret. Analiz29, Metody Diskret. Anal. v Teorii Kodov i Skhem (1976), 3–10

    work page 1976

  45. [45]

    Voigt,List colourings of planar graphs, Discrete Math.120(1993), 215–219

    M. Voigt,List colourings of planar graphs, Discrete Math.120(1993), 215–219

    work page 1993

  46. [46]

    Voigt,A not3-choosable planar graph without3-cycles, Discrete Math.146(1995), 325–328

    M. Voigt,A not3-choosable planar graph without3-cycles, Discrete Math.146(1995), 325–328

    work page 1995

  47. [47]

    Wang,Some recent advances on the choosability of signed graphs, preprint (2020)

    Y. Wang,Some recent advances on the choosability of signed graphs, preprint (2020)

    work page 2020

  48. [48]

    Zaslavsky,Signed graphs, Discrete Appl

    T. Zaslavsky,Signed graphs, Discrete Appl. Math.4(1982), 47–74; Erratum:5(1983), 248

    work page 1982

  49. [49]

    Zaslavsky,Signed graph coloring, Discrete Math.39(1982), 215–228

    T. Zaslavsky,Signed graph coloring, Discrete Math.39(1982), 215–228

    work page 1982

  50. [50]

    Zaslavsky,Chromatic invariants of signed graphs, Discrete Math.42(1982), 287–312

    T. Zaslavsky,Chromatic invariants of signed graphs, Discrete Math.42(1982), 287–312

    work page 1982

  51. [51]

    Zaslavsky,Vertices of localized imbalance in a biased graph, Proc

    T. Zaslavsky,Vertices of localized imbalance in a biased graph, Proc. Amer. Math. Soc.101 (1987), 199–204. 16

    work page 1987