Pith. sign in

REVIEW 2 major objections 3 minor 11 references

Truncated degree AT-orientations of outerplanar graphs

T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read Every 2-connected outerplanar graph except odd cycles is 5-truncated degree-AT.

desk verdict The main induction is blocked by a false ear-chain assertion; the result may be true but the proof doesn't cover all cases. read the letter →

arxiv 2412.20811 v1 pith:WVS342CF submitted 2024-12-30 math.CO

Chenglong Deng , Xuding Zhu This is my paper · ORCID
classification math.CO MSC 05C1505C10
keywords AT-orientationouterplanargraphspaintabilitylistcoloringtruncateddegreechoosabilityarc-weightedorientationsear-chaindecomposition
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

This paper proves sharp bounds for a stronger form of list coloring called AT-orientations. An AT-orientation is an orientation of a graph in which the number of even Eulerian sub-digraphs differs from the number of odd ones; such an orientation is known to guarantee list-colorability from lists whose sizes match the outdegree caps, including in the online 'paintability' version. The first result says every 2-connected outerplanar graph other than an odd cycle has a 5-truncated degree-AT orientation, meaning each vertex v is allowed min{5, d_G(v)} colors. The second says every 2-connected bipartite outerplanar graph has a 4-truncated degree-AT orientation. If correct, these results upgrade earlier choosability theorems for outerplanar graphs to online paintability and extend them from maximal to all 2-connected outerplanar graphs.

What carries the argument

The load-bearing object is an arc-weighted orientation (D,w) together with a chosen orientation of a distinguished set of boundary edges S. An arc-weighted Eulerian sub-digraph is one where weighted in- and out-degree agree at every vertex; the orientation counts as AT if the number of even-sized such sub-digraphs differs from the number of odd-sized ones. The paper works with the stronger property that the total number of Eulerian sub-digraphs is odd. The induction removes an ear-chain, a chain of cycles attached to a base edge, orients the removed edges in a canonical directed-path pattern, and in some cases reverses a few edges or doubles one weight to balance outdegree demands. Oriented boundary edges S act as a 'bank': an edge oriented out of v tightens v's allowance while loosening the other endpoint's, and the slack is repaid when the ear-chain is reinserted. Verifying the final theorem reduces to checking, case by case, that the newly added arcs contribute no directed cycles and hence no new Eulerian sub-digraphs, or that they come in canceling pairs, and that the outdegree inequalities transfer.

What would settle it

To disprove the 5-truncated claim, it would suffice to exhibit a 2-connected outerplanar graph G, not an odd cycle, such that every orientation D of G either has some vertex v with d+D(v) >= min{5, d_G(v)} or has equal numbers of even and odd Eulerian sub-digraphs. A more targeted check would search for a graph whose every arc-weighted orientation meeting the outdegree bound min{4, d_G(v)-1} has an even total number of Eulerian sub-digraphs, since the proof's parity step would fail precisely there.

Watch

Extended reading notes

Core claim

The central discovery is that the 5- and 4-truncated degree list-coloring results for outerplanar graphs hold in the stronger Alon-Tarsi-orientation form, and therefore in the online paintability model. Theorem 2 asserts that every 2-connected outerplanar graph that is not an odd cycle has an AT-orientation whose outdegree at each vertex v is at most min{4, d_G(v)-1}, which is exactly the 5-truncated degree condition. Theorem 3 asserts that every 2-connected bipartite outerplanar graph has an AT-orientation with outdegree at most min{3, d_G(v)-1}, the 4-truncated condition. The proof establishes these by induction on an ear-chain decomposition, maintaining a stronger invariant: for an auxiliary set of boundary edges S with an orientation, there is an arc-weighted orientation with weighted outdegree at most min{4-2d+S(v), d_G(v)-1+d-S(v)}, and with an odd number of Eulerian sub-digraphs. The oriented boundary edges act as a bank, transferring outdegree allowances between vertices when an ear-chain is removed and later reattached.

Load-bearing premise

The load-bearing premise is the unproved assertion that every 2-connected non-cycle outerplanar graph can be decomposed by removing a chain of cycles attached to one base edge, together with the known equivalence between AT-orientations and arc-weighted orientations; if either step failed, the constructed orientations would not certify the list-coloring bounds.

Editorial extensions

If this is right

  • Every 2-connected outerplanar graph other than an odd cycle is 5-truncated degree-paintable: Painter wins the online list-coloring game when each vertex gets min{5, d_G(v)} tokens.
  • Every 2-connected bipartite outerplanar graph is 4-truncated degree-paintable.
  • The bounds are tight: some 2-connected outerplanar graphs fail 4-truncated degree choosability, and some bipartite outerplanar graphs fail 3-truncated degree choosability, so no smaller constants are possible.
  • Because an AT-orientation implies ordinary list colorability, the results also settle the question for all 2-connected outerplanar graphs, not just maximal ones.
  • The arc-weighted 'bank' induction provides a local certificate for truncated-degree AT-orientations, which is a more flexible tool than earlier DP-coloring arguments for this family.

Reading between the lines

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

  • The bank-system induction may transfer to other graph classes: whenever a class has a bounded ear-chain decomposition and a way to orient boundary edges, the same parity-and-outdegree recipe could yield truncated-degree AT bounds with constants tied to the ear width.
  • Because the theorem is constructive, it could be turned into an algorithm that, given an outerplanar graph, produces a degree-truncated AT-orientation and hence an online list-coloring strategy by repeated ear-chain removal.
  • The thresholds 5 and 4 match the ordinary chromatic numbers of outerplanar and bipartite outerplanar graphs, suggesting truncated-degree AT-orientations may be a route to proving colorability exactly at the 'truncated' analogue of the chromatic number for other sparse graph families.
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

2 major / 3 minor

Summary. The paper studies truncated degree Alon-Tarsi (AT) orientations of outerplanar graphs. It proves two main theorems: (Theorem 2) every 2-connected outerplanar graph that is not an odd cycle is 5-truncated degree-AT, and (Theorem 3) every 2-connected bipartite outerplanar graph is 4-truncated degree-AT. Using the standard Alon-Tarsi and Schauz results, these imply the same graphs are 5- and 4-truncated degree-paintable, respectively, extending Hutchinson's earlier choosability results to the online setting. The proofs are inductive and construct arc-weighted orientations with a 'bank system' of oriented boundary edges.

Significance. If the main theorems are correct, the paper provides a genuine advance: it extends Hutchinson's truncated degree choosability results for outerplanar graphs to the stronger online paintability framework and to AT-orientations, for all 2-connected outerplanar graphs rather than only maximal ones. The arc-weighted orientation machinery and the parity-based induction are a natural and potentially reusable tool. However, the proof of Theorem 2 has a substantial gap in the decomposition step (the ear-chain existence assertion), and the cycle base case contains a false parity claim. The core idea is promising, but the manuscript in its current form does not rigorously establish Theorem 2.

major comments (2)
  1. [Section 2, Definition 5 and Lemma 1] The proof of Lemma 1 begins with the assertion that every 2-connected outerplanar graph that is not a cycle contains an ear-chain F as defined in Definition 5. This assertion is false. For the 5-vertex maximal outerplanar fan with outer cycle (1,2,3,4,5) and chords (1,3) and (1,4), the only vertices of degree 2 are 2 and 5. Any induced cycle C whose internal vertices have no other incident edges must be a triangle containing exactly one degree-2 vertex, e.g., (1,2,3) or (1,5,4). For such a triangle, the possible root edges for an ear are the two edges incident to the base edge; attaching an ear to either would require a second path whose internal vertices are degree 2, but the remaining degree-2 vertex is not adjacent to both required endpoints. Hence this graph has no ear-chain. The same obstruction occurs for every maximal outerplanar graph with more than three vertices. Consequently, the induction step in Lemma 1 does not apply to a broad family of graphs covered by Theorem 2, and the proof of Theorem 2 is incomplete.
  2. [Section 2, base case for cycles in Lemma 1] In the case where G is a cycle, the orientation D is defined as a directed cycle with arcs (v_i,v_{i+1}) for i=1,...,n-1 and (v_1,v_n). The text states that the only Eulerian subdigraph is the empty subdigraph, implying |E(D,w)| is odd. This is incorrect: the full set of arcs is also Eulerian, since every vertex has one incoming and one outgoing arc, so |E(D,w)| = 2, which is even. The valid-orientation condition requires |E(D,w)| odd. The issue is repairable, for example by orienting the edge v_1v_n also from v_1 to v_n so that v_1 has outdegree 2 and the full arc set is not Eulerian, but as written the base case is wrong and the parity condition is not satisfied.
minor comments (3)
  1. [Section 3, Lemma 3] The induction is said to be on |f(G)|, but f(G) is never defined; presumably it denotes the number of faces of the outerplane embedding. Please define this notation and justify why the chosen leaf face exists with the stated degree-2 internal vertices.
  2. [Section 3, proof of Lemma 3] In the first case (v_1v_2 not in S), the text asserts d^-_{\vec S}(v_j) >= 1 for j=2,...,2i-1, but this need not hold, e.g., if no edge of S is incident to v_j or if the only incident S-edge is oriented out of v_j. The inequality can still be verified because d_G(v_j)=2, so the weaker bound d_G(v_j)-1 = 1 suffices; please correct the justification.
  3. [Throughout] There are numerous typos and formatting glitches, such as missing symbols in the abstract and undefined notation 'N = {0, 1, . . . ,}' in the introduction. A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the theorems are derived from external Alon–Tarsi and arc-weighted orientation results, not from their own inputs.

full rationale

The paper's central claim is Theorem 2 and Theorem 3, proved by constructing an arc-weighted orientation with a parity condition on the number of Eulerian subdigraphs. The only external tools used are the arc-weighted AT characterization from Kozik and Podkanowicz [7], the Alon–Tarsi choosability theorem [1], and Schauz's paintability theorem [9]; these are independent results, not self-citations, and they do not contain the paper's conclusion. The oriented boundary-edge 'bank system' is an auxiliary inductive device: the inequality d+_{(D,w)}(v) ≤ min{4, d_G(v)−1} for S=∅ is exactly the needed f-AT condition, and the oddness of |E(D,w)| is a sufficient certificate for nonzero diff(D,w), not a restatement of the target. No fitted parameter is renamed as a prediction, and no equation reduces by construction to its input. The only notable weakness is a structural assertion before Lemma 1 — 'it is easy to verify that G contains an ear chain F' — which is unproved and may be a correctness gap for some maximal outerplanar graphs, but this is a missing proof, not circularity. The self-citations [8] and [11] appear only in the introduction as context and are not load-bearing in the proofs. Therefore the derivation chain is self-contained with respect to circularity.

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

The paper introduces no fitted constants or new mathematical entities. Its dependencies are standard graph-coloring theorems (Alon-Tarsi, Schauz) and an arc-weighted equivalence cited from [7]. The bank system of oriented boundary edges is an internal proof device, not an invented entity.

assumptions (4)
  • domain assumption A graph is f-AT if and only if it has an arc-weighted orientation with d+_(D,w)(v) < f(v) for all v.
    Invoked in Section 2 after Theorem 2 is stated, citing [7]. The entire proof of Theorem 2 constructs arc-weighted orientations rather than ordinary AT-orientations.
  • domain assumption Every 2-connected outerplanar graph that is not a cycle contains an ear-chain F of the form defined in Definition 5.
    Used in Lemma 1 to remove F and apply induction; the paper says 'it is easy to verify' but gives no proof.
  • standard math Every orientation of a bipartite graph is an AT-orientation (Lemma 2).
    Used to conclude Theorem 3 from the orientation constructed in Lemma 3; the proof is a one-sentence argument and it is correct.
  • standard math Alon-Tarsi theorem and Schauz theorem: an f-AT graph is f-choosable and f-paintable.
    Cited as [1] and [9] and used to convert Theorems 2 and 3 into choosability and paintability corollaries.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Truncated degree AT-orientations of outerplanar graphs." pith.science (2026). https://pith.science/paper/WVS342CF

@misc{pith2026241220811,
  author       = {Pith},
  title        = {Pith review of: Truncated degree AT-orientations of outerplanar graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WVS342CF}},
  note         = {Machine review of arXiv:2412.20811}
}
abstract

An AT-orientation of a graph $G$ is an orientation $D$ of $G$ such that the number of even Eulerian sub-digraphs and the number of odd Eulerian sub-digraphs of $D$ are distinct. Given a mapping $f: V(G) \to \mathbb{N}$, we say $G$ is $f$-AT if $G$ has an AT-orientation $D$ with $ < f(v)$ for each vertex $v$. For a positive integer $k$, we say $G$ is $k$-truncated degree-AT if $G$ is $f$-AT for the mapping $f$ defined as $f(v) = \min #{k, d_G(v)#} $. This paper proves that 2-connected outerplanar graphs other than odd cycles are $5$-truncated degree-AT, and 2-connected bipartite outerplanar graphs are $4$-truncated degree-AT. As a consequence, 2-connected outerplanar graphs other than odd cycles are $5$-truncated degree paintable, and 2-connected bipartite outerplanar graphs are $4$-truncated degree paintable. This improves the result of Hutchinson in [On list-coloring outerplanar graphs], where it was proved that maximal 2-connected outerplanar graphs other than are 5-truncated degree-choosable, and 2-connected bipartite outerplanar graphs are 4-truncated degree-choosable.

Figures

Figures reproduced from arXiv: 2412.20811 by the authors.

Figure 1
Figure 1. Two example ear-chains. As G is a 2-connected outerplanar graph and G is not a cycle, it is easy to verify that G contains an ear chain F. Assume F is an ear chain in G. Assume F consists an induced cycle C = (v1, v2, . . . , vs) with base edge v1vs, and ears H1, H2, . . . , Ht . For j = 1, 2, . . . , t, Hj is an induced cycle (uj,1, uj,2, . . . , uj,mj ) with root edge uj,1uj,mj = vij vij+1, where 1 ≤ i1 < i2 < . .… view at source ↗
Figure 2
Figure 2. Orientations DF for Case 1 and Case 2. Case 3. v1v2 is the root edge of ear H1 and u1,1u1,2 ∈/ S. Subcase 3.1. v2v3 is the root edge of H2 and u2,1u2,2 ∈ S. In this case, (DF , wF ) is obtained from the canonical orientation by reversing the direction of edges v1v2 and u2,1u2,2, and also change the weight of (u1,1, u1,2) to 2. The other arcs have weight 1. See [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. (a). (1) Again, the arcs (u1,1, u1,2) is not contained in any Eulerian subdigraph, and no arc in DF −{(u1,1, u1,2)} is contained in a directed cycle of (D, w)−{(u1,1, u1,2)}. Hence E new(D, w) = ∅. (2) It follows from the definition that l(v1) = 2. As dG(v1) = dG′(v1)+2, d + S⃗ (v1) = d + S⃗′ (v1)−1, and d − S⃗ (v1) = d − S⃗′ (v1), we conclude that r(v1) ≥ 2. So l(v1) ≤ r(v1). (3) For v ∈ (V (F) − {v1, v2, vs}), d +… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: (b). (1) As no arc in E(F) is contained in a directed cycle, E new(D, w) = ∅. (2) It follows from definition that l(v1) = 0 . As dG(v1) = dG′(v1) + 2, d + S⃗ (v1) = d + S⃗′ (v1), and d − S⃗ (v1) = d − S⃗′ (v1), we conclude that r(v1) ≥ 0. (3) For v ∈ (V (F) − {v1, v2, …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 9 canonical work pages

  1. [7]

    Kozik and B

    J. Kozik and B. Podkanowicz. Schnyder woods and Alon-Tarsi number of planar graphs. Electron. J. Combin., 31(1):Paper No. 1.59, 13, 2024

    work page 2024

  2. [1]

    Alon and M

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

    work page 1992

  3. [2]

    D. W. Cranston, A. Pruchnewski, Z. Tuza, and M. Voigt. List colorings ofK5-minor-free graphs with special list assignments.J. Graph Theory, 71(1):18–30, 2012

    work page 2012

  4. [3]

    Duraj, G

    L. Duraj, G. Gutowski, and J. Kozik. Chip games and paintability.Electron. J. Combin. , 23(3):Paper 3.3, 12, 2016

    work page 2016

  5. [4]

    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. B , 129:38–54, 2018

    work page 2018

  6. [5]

    Erdős, A

    P. Erdős, A. L. Rubin, and H. Taylor. Choosability in graphs. InProceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing (Humboldt State Univ., Arcata, Calif., 1979) , volume XXVI ofCongress. Numer., pages 125–157. Utilitas Math., Winnipeg, MB, 1980

    work page 1979

  7. [6]

    J. P. Hutchinson. On list-coloring outerplanar graphs.J. Graph Theory, 59(1):59–74, 2008

    work page 2008

  8. [8]

    S. Lo, C. Wang, H. Zhou, and X. Zhu. DP-5-truncated-degree-colourability of K2,4-minor free graphs. arXiv:2312.15962

    arXiv

Show all 11 references
  1. [9]

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

    2009

  2. [10]

    V. G. Vizing. Coloring the vertices of a graph in prescribed colors.Diskret. Analiz, (29):3–10, 101, 1976

    1976

  3. [11]

    H. Zhou, J. Zhu, and X. Zhu. Arc-weighted acyclic orientations and variations of degeneracy of graphs. arXiv:2308.15853. 12

    arXiv

Pith tools

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