Every signed planar graph is 5 5 -choosable: A short proof and refinements
Pie Désiré EBODE ATANGANA 1, Maxwell NDOGNKON MANGA 2 · 2026
Read Every signed planar graph is 5 5 -choosable: A short proof and refinements by Pie Désiré EBODE ATANGANA 1, Maxwell NDOGNKON MANGA 2 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-22860.txt.
Introduction
Ebode Atangana and Ndognkon Manga give a short, self-contained proof that every signed planar graph is 5-choosable, meaning each vertex can be colored from any list of five colors respecting edge signs. Their signature-blind induction inserts one sign factor uniformly, so it reduces to Thomassen's classic proof when all signs are positive. The same argument yields refinements, including 3-choosability for outerplanar signed graphs and a fast list-coloring algorithm.
Catalog record
| CREATOR | Pie Désiré EBODE ATANGANA 1, Maxwell NDOGNKON MANGA 2 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49991 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.22860
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Every signed planar graph is 5 5 -choosable: A short proof and refinements Pie Désiré EBODE ATANGANA 1, Maxwell NDOGNKON MANGA 2 Abstract A signed graph is a pair ( G , σ ) (G,\sigma) in which G G is a finite simple graph and σ : E ( G ) → { + 1 , − 1 } \sigma:E(G)\to\{+1,-1\} is a signature . Following Máčajová–Raspaud–Škoviera and Jin–Kang–Steffen, a proper coloring of ( G , σ ) (G,\sigma) is a map c : V ( G ) → ℤ c:V(G)\to\mathbb{Z} with c ( u ) ≠ σ ( u v ) c ( v ) c(u)\neq\sigma(uv)\,c(v) for every edge u v uv , and ( G , σ ) (G,\sigma) is signed k k -choosable if such a coloring exists from any list assignment L L with | L ( v ) | ≥ k |L(v)|\geq k . In a celebrated two-page note, Thomassen proved that every planar graph is 5 5 -choosable, and Jin, Kang, and Steffen subsequently extended this to signed planar graphs. Our principal contribution is a short, self-contained, and signature-blind proof of the latter: the inductive bookkeeping inserts one factor of σ ( ⋅ ) \sigma(\cdot) uniformly into every constraint, so that with σ ≡ + 1 \sigma\equiv+1 the argument reduces verbatim to Thomassen’s original. From the strengthened extension statement ( Theorem 1.4 ) we deduce the main result ( Theorem 1.3 : χ ℓ s ( G , σ ) ≤ 5 \chi_{\ell}^{s}(G,\sigma)\leq 5 for every planar signed graph), the Máčajová–Raspaud–Škoviera signed Five-Color Theorem in the symmetric palette N 2 = { − 2 , − 1 , 0 , 1 , 2 } N_{2}=\{-2,-1,0,1,2\} , the Switching Invariance Lemma, 3 3 -choosability of outerplanar signed graphs, 1 1 -defective signed 4 4 -choosability of planar signed graphs, a sandwich inequality relating χ ℓ s \chi_{\ell}^{s} to the unsigned and “positive” choice numbers, and a polynomial-time list-coloring algorithm. Voigt’s planar non- 4 4 -choosable graph and Mirzakhani’s smaller variant show the bound 5 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. Keywords: signed graph; list coloring; choosability; planar graph; near-triangulation; switching; Thomassen’s theorem. 2020 Mathematics Subject Classification: 05C15; 05C22; 05C10. 1 Introduction The chromatic number \chia(G) of a graph G is the smallest k for which the vertices of G admit a proper k -coloring. The Four Color Theorem of Appel and Haken [ 3 , 33 ] states \chia(G)\leq 4 for every planar graph; its weaker but elementary predecessor, the Five Color Theorem , was already known to Heawood [ 17 ] . Standard references for this classical material are [ 5 , 11 , 19 ] . Building on this theory, one can ask what happens when colors are not freely chosen but must come from prescribed lists. A list assignment for G is a map L associating to each v\in V(G) a finite set L(v) of admissible colors. The graph G is L -colorable if it admits a proper coloring c with c(v)\in L(v) for every v , and k -choosable if it is L -colorable for every list assignment with |L(v)|\geq k . The smallest such k , denoted \chil(G) , is the list chromatic number (or choice number ). List coloring superficially resembles ordinary coloring, but \chil(G) can be strictly larger than \chia(G) , so analogues of classical theorems do not come for free. The notion of choosability was introduced independently by Vizing [ 44 ] and by Erdős, Rubin and Taylor [ 15 ] . Both papers asked whether every planar graph is 5 -choosable. Voigt [ 45 ] showed that planar graphs need not even be 4 -choosable: she exhibited a planar graph on 238 vertices and an associated list assignment of size 4 admitting no proper coloring. A smaller witness on 63 vertices was later found by Mirzakhani [ 29 ] . The matching upper bound was established by Thomassen [ 41 ] , who proved that every planar graph is 5 -choosable. Thomassen’s proof, occupying less than a page, is now standard fare in graph theory courses; it proceeds by induction on a strengthened statement involving two adjacent precolored boundary vertices. We turn now from ordinary graphs to signed graphs. A signed graph (G,\sigma) is a pair where G is a graph and \sigma:E(G)\to\{+1,-1\} is a signature ; the notion was introduced by Harary [ 16 ] in the context of social psychology and developed systematically by Zaslavsky [ 48 , 50 , 51 ] . Edges e with \sigma(e)=+1 are positive and those with \sigma(e)=-1 are negative ; the sign of a closed walk is the product of the signs of its edges, and (G,\sigma) is balanced if every cycle is positive. Switching at U\subseteq V(G) negates the sign of every edge with exactly one endpoint in U , defining an equivalence relation on signatures; by Zaslavsky’s theorem [ 48 ] , \sigma is balanced iff it is switching-equivalent to the all-positive signature. Beyond their original psychological motivation, signed graphs arise in the geometry of root systems and arrangements [ 48 , 50 ] , in flow theory [ 6 ] , and in the chromatic theory developed by Zaslavsky, Máčajová–Raspaud–Škoviera, and others; for recent surveys see [ 31 , 36 ] . Several non-equivalent proposals for the chromatic theory of signed graphs appear in the literature, and the choice of framework matters for a list-coloring statement. Zaslavsky’s original definition [ 48 , 49 ] uses “signed colors” from the set \{0,\pm 1,\dots,\pm k\} and treats the zero color asymmetrically. Máčajová, Raspaud, and Škoviera [ 28 ] reformulated the basic notion in a way that more naturally generalizes the chromatic number and aligns with the homomorphism viewpoint of Naserasr, Rollová, and Sopena [ 30 ] . We adopt the definition that is intrinsic to the integer arithmetic of the signature, formalized as follows. Definition 1.1 (Coloring of signed graphs) . A coloring of a signed graph (G,\sigma) is a map c\colon V(G)\to\mathbb{Z} with c(u)\;\neq\;\sigma(uv)\,c(v)\qquad\text{for every edge }uv\in E(G). Equivalently, on positive edges uv one requires c(u)\neq c(v) , while on negative edges uv one requires c(u)+c(v)\neq 0 . Definition 1.2 (List coloring of signed graphs) . A list assignment for (G,\sigma) is a map L\colon V(G)\to 2^{\mathbb{Z}} assigning to each v a finite set L(v)\subseteq\mathbb{Z} . An L -coloring is a coloring (in the sense of Definition 1.1 ) with c(v)\in L(v) for every v . The signed graph (G,\sigma) is signed k -choosable if it admits an L -coloring whenever |L(v)|\geq k for all v , and the signed list chromatic number (or signed choice number ) is \chi_{\ell}^{s}(G,\sigma)\;:=\;\min\bigl\{k\in\mathbb{N}:(G,\sigma)\text{ is signed }k\text{-choosable}\bigr\}. Two consistency checks are in order. First, when \sigma\equiv+1 , the constraint c(u)\neq\sigma(uv)c(v) becomes c(u)\neq c(v) , the classical proper-coloring condition; hence \chia(G,+1)=\chia(G) and \chi_{\ell}^{s}(G,+1)=\chil(G) , so the signed framework specializes correctly to the unsigned one. Second, our framework is consistent with the symmetric palette of Máčajová, Raspaud, and Škoviera [ 28 ] : those authors restrict c to take