{"id":"d2f813c8-37cb-4cb0-8c20-a9915cdf7213","arxiv_id":"2412.20811","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every 2-connected outerplanar graph other than an odd cycle admits a 5-truncated degree Alon-Tarsi orientation, and every 2-connected bipartite outerplanar graph admits a 4-truncated degree one.","lead":"This paper proves that every 2-connected outerplanar graph that is not an odd cycle has a 5-truncated degree Alon-Tarsi orientation, and every 2-connected bipartite outerplanar graph has a 4-truncated one. These orientations imply strong online list-coloring (paintability) results, improving an earlier theorem of Hutchinson.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The ear-chain decomposition asserted before Lemma 1 fails for the 5-vertex maximal outerplanar fan, so the induction proving Theorem 2 does not cover all cases.","rationale":"The reader's weakest assumption correctly flags the unproved ear-chain existence claim. My stress test strengthens this: the claim is not merely unproved but false for the 5-vertex maximal outerplanar fan, a graph squarely in the scope of Theorem 2. Because Lemma 1 is the only proof of Theorem 2, this is load-bearing: the induction cannot start for an infinite family of maximal outerplanar graphs unless a different decomposition or a separate case is supplied. I do not claim the theorem itself is false; indeed, the result is plausible and likely repairable by handling fans directly or by using a more permissive ear decomposition. The verdict therefore remains conditional rather than accept or reject. Other issues, such as the parity argument in Case 1 of Lemma 1 appearing to count nonempty Eulerian subgraphs in an acyclic orientation, are secondary and do not change the overall assessment.","tokens_in":13831,"tokens_out":33413,"duration_ms":348665,"concrete_test":"Write a small program that enumerates all induced cycles C and all candidate ears H in the fan graph with outer 5-cycle 1-2-3-4-5-1 and chords 1-3, 1-4, checking the conditions of Definition 5: internal vertices of C have no other incident edges, each ear has all internal vertices of degree 2, and at least one ear is rooted at a non-base edge of C. The enumeration will return no valid ear-chain, confirming that the asserted decomposition is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 1 rests on the assertion '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.' This assertion is false as stated. In the 5-vertex maximal outerplanar fan (outer 5-cycle 1-2-3-4-5-1 plus chords 1-3 and 1-4), exactly two vertices have degree 2. Definition 5 requires the internal vertices of the cycle C to have no other incident edges in G, and each ear H to have all its internal vertices of degree 2 in G. Any cycle whose internal vertices all have degree 2 in this fan is a triangle using one of the two degree-2 vertices; an ear attached to a non-base edge of such a triangle would need a second path whose internal vertices are the other degree-2 vertex, but no such path has both endpoints on an allowed root edge. Hence the fan contains no ear-chain satisfying Definition 5. Since Lemma 1 is the entire proof of Theorem 2, the induction has no starting decomposition for maximal outerplanar graphs of this type. The theorem may still be true, and the graph may admit a direct construction, but the proof as written does not establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":14045,"tokens_out":15261,"duration_ms":135829,"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":[{"comment":"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.","section":"Section 2, Definition 5 and Lemma 1"},{"comment":"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.","section":"Section 2, base case for cycles in Lemma 1"}],"minor_comments":[{"comment":"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.","section":"Section 3, Lemma 3"},{"comment":"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.","section":"Section 3, proof of Lemma 3"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The ear-chain gap is especially concerning because it removes exactly the maximal outerplanar graphs that are the original focus of Hutchinson's theorem. The proof of Theorem 2 as written does not cover these graphs, so the central claim is not established. I believe the approach may be fixable — for instance, by replacing the single ear-chain decomposition with a sequential ear decomposition or by adding a separate direct construction for maximal outerplanar graphs — but that is a significant revision rather than a local edit. The bipartite theorem (Theorem 3) appears more solid, though the proof needs some clarifications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the quick take. The paper's main claim is that every 2-connected outerplanar graph other than an odd cycle is 5-truncated degree-AT (and the bipartite 4-analog), which would upgrade Hutchinson's list-coloring results to Alon-Tarsi orientations and online paintability. That is a genuine and worthwhile strengthening, and the arc-weighted \"bank\" framework is a clever device. But I found a hole in the proof of Lemma 1, and it is load-bearing.\n\nThe problem is the claim, right before the induction, that every 2-connected outerplanar graph that is not a cycle contains an ear-chain. That is false. Take the maximal outerplanar fan on vertices 1..5 with chords 1-3 and 1-4. The only degree-2 vertices are 2 and 5. Definition 5 requires the internal vertices of the base cycle C to have degree 2 in G, and every ear to have internal vertices of degree 2. No cycle in this fan satisfies the condition: each triangle contains at most one degree-2 vertex, and no other path exists to form an ear on the non-base edges. So the fan has no ear-chain, and the induction cannot start for it. Since this is the entire mechanism for Theorem 2, the proof as written does not cover all cases.\n\nI don't see this as fatal to the truth of the theorem—a direct construction for such fans is plausible, and the rest of the case analysis is careful. But it is not a minor typo; the claimed decomposition is essential. The parity argument for |E(D,w)| being odd looks plausible, and the bipartite proof (Theorem 3) uses a standard ear argument that seems fine. The equivalence borrowed from [7] is also reasonable.\n\nSo: the paper is worth reading if you work on AT-orientations or online list coloring, and it deserves a referee's time—the gap is specific and likely fixable. But I wouldn't cite it or rely on Theorem 2 until the proof is repaired.","headline":"The main induction is blocked by a false ear-chain assertion; the result may be true but the proof doesn't cover all cases.","tokens_in":14580,"tokens_out":3995,"would_cite":false,"duration_ms":36213,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every 2-connected outerplanar graph except odd cycles is 5-truncated degree-AT.","keywords":["AT-orientation","outerplanar graphs","paintability","list coloring","truncated degree choosability","arc-weighted orientations","ear-chain decomposition"],"falsifier":"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.","tokens_in":13620,"feed_emoji":"🎨","tokens_out":10123,"duration_ms":86756,"temperature":0.7,"pith_summary":"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.","feed_headline":"Outerplanar graphs (except odd cycles) are 5-truncated degree-AT","feed_subtitle":"The same graphs are 5- and 4-truncated degree-paintable, an online list-coloring guarantee with tight constants.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the theorem that an AT-orientation with the stated outdegree bounds implies list colorability, turning the orientation result into a choosability result.","marker":"[1]"},{"why":"The earlier 5- and 4-truncated degree-choosability results for maximal outerplanar graphs that this paper extends and tightens.","marker":"[6]"},{"why":"Establishes the arc-weighted characterization of AT-orientations that the proof uses as its certificate.","marker":"[7]"},{"why":"The DP-coloring result for K2,4-minor-free graphs that already implied 5-truncated degree choosability of all 2-connected outerplanar graphs, providing the broader context.","marker":"[8]"},{"why":"Supplies the theorem that an AT-orientation implies paintability, yielding the online list-coloring corollary.","marker":"[9]"}],"fun_headline_variants":["2-connected outerplanar graphs: 5-AT, bipartite: 4-AT","Outerplanar graphs (not odd cycles) are 5-AT; bipartite: 4-AT","Tighter AT-orientations for outerplanar graphs: 5 and 4","Outerplanar graphs get 5-AT, bipartite ones 4-AT","5-AT for outerplanar graphs, 4-AT for bipartite ones"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["2-connected outerplanar graphs: 5-AT, bipartite: 4-AT","Outerplanar graphs (not odd cycles) are 5-AT; bipartite: 4-AT","Tighter AT-orientations for outerplanar graphs: 5 and 4","Outerplanar graphs get 5-AT, bipartite ones 4-AT","5-AT for outerplanar graphs, 4-AT for bipartite ones"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002087,"raw_usage":{"total_tokens":8186,"prompt_tokens":1088,"completion_tokens":7098,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":704,"completion_tokens_details":{"reasoning_tokens":6978}},"tokens_in":704,"tokens_out":7098,"duration_ms":45174,"temperature":1.0,"reasoning_tokens":6978,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:12:07.223328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Alon and M","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that an AT-orientation with the stated outdegree bounds implies list colorability, turning the orientation result into a choosability result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The earlier 5- and 4-truncated degree-choosability results for maximal outerplanar graphs that this paper extends and tightens."},{"cited_title":"Kozik and B","cited_arxiv_id":null,"evidence_quote":"Establishes the arc-weighted characterization of AT-orientations that the proof uses as its certificate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that an AT-orientation implies paintability, yielding the online list-coloring corollary."}],"review_version":1}