{"id":"29483fa7-831b-40f4-a08e-bfeada1a9711","arxiv_id":"1909.02612","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every k-tree and partial k-tree admits an online nonrepetitive coloring with 4^k colors, and online paths need only 12 colors.","lead":"This paper proves that any graph whose structure is close to a tree (tree-width at most k) can be colored online, without any path repeating its color pattern, using 4^k colors. Trees, cycles, and series-parallel graphs need at most 16 colors, and paths need 12, matching what is possible without the online constraint.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the terse universality/compactness steps are routine and the central 4^k bound argument is sound.","rationale":"The reader's weakest_assumption pointed at the universal embedding and the compactness step. I agree those are the least formal parts, but after reconstructing the induction I find the embedding claim correct and the compactness argument standard. There is also a minor over-claim about embeddings of isomorphic prefixes being identical, but the proof never uses that stronger property; incremental extension of a chosen injection is sufficient. Therefore no load-bearing concern remains. The verdict should stay as the reader set it (CONDITIONAL), because the paper would benefit from spelling out these proofs, but I would not move it to REJECT or UNVERDICTED on correctness grounds. Agreement is partial because the flagged step is indeed the one to check, though I do not consider it a real vulnerability.","tokens_in":6326,"tokens_out":39159,"duration_ms":453109,"concrete_test":"Write out the induction for the embedding explicitly: (Base) U_1=K_{k+1} contains the initial complete graph. (Step) assume T_{t-1} embeds into U_t; for a new vertex with neighbor clique C in T_{t-1}, note that the image of C is a k-clique of U_t, and U_{t+1} contains the fresh vertex added for that clique; extend the injection there. Also verify the partial-k-tree extension step by proving every clique of size at most k in a k-tree T_{t-1} is contained in a k-clique, with the obvious handling when |V(T_{t-1})|<k. If both inductions close, the universality concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"We find no load-bearing flaw in Theorem 1.2. The only genuinely unproved ingredient is the asserted universal embedding of every finite online k-tree into U. This step is true: inductively, after t steps the current k-tree completion T_t embeds into U_{t+1}; a new vertex whose neighbors form a k-clique C in T_t maps to the vertex that U_{t+2} adds for the image of C, which is fresh because U_{t+1} contains all earlier images. For partial k-trees the same embedding works after completing the partial graph to a k-tree T_t by adding the new vertex to any k-clique containing its specified neighbours; such a k-clique exists in a k-tree because every clique is contained in a maximal (k+1)-clique. The Koenig/compactness passage from finite colorings of U_i to an infinite coloring of U is also standard: colorings of the nested finite U_i form an infinite finitely branching tree, and any infinite branch yields a coloring in which every finite path of U is nonrepetitive. These are omissions in exposition rather than holes in the argument, so the conditional verdict is not driven by a correctness risk in the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies an online variant of nonrepetitive graph coloring in which vertices arrive one by one and must be colored immediately so that the current graph remains nonrepetitively colored. The main result, Theorem 1.2, states that every online k-tree can be colored nonrepetitively online with 4^k colors. The proof constructs an infinite universal k-tree U, uses the offline nonrepetitive 4^k-coloring theorem of Kündgen and Pelsmajer for each finite induced subgraph of U, and passes to a coloring of the whole U via König's lemma. The coloring of any online k-tree is then obtained by embedding it incrementally into U. Corollary 1.3 extends the result to partial k-trees, i.e., graphs of tree-width at most k, and Corollary 1.4 specializes to cycles, trees, and series-parallel graphs with 16 colors. Theorem 1.5 improves the bound to 12 colors for online paths via a similar universal-graph construction using the fact that outerplanar graphs are 12-nonrepetitively colorable offline. The final section discusses online nonrepetitive list-colorings, proves a left-to-right path list-coloring result from a lemma of Kozik and Micek, and poses open problems.","tokens_in":6479,"tokens_out":5941,"duration_ms":57642,"significance":"If the proof is correct, the paper settles the online nonrepetitive coloring problem for graphs of bounded tree-width with the same color count as the known offline bound, which is a clean and genuinely useful result. The universal-graph-plus-compactness method is elegant and likely to be reusable. The paper also introduces a directed/vertical variant of nonrepetitive colorings that may be of independent interest, and it explicitly connects to simultaneous independent work on online paths. The main limitations are presentational: two crucial universality statements are asserted without proof, and the reduction from partial k-trees to k-trees is compressed into a single sentence. These are fixable but require added detail for the central claims to be fully substantiated.","major_comments":[{"comment":"The proof relies on the existence of incremental injections inj_{G_t} embedding every online k-tree G_t into the universal k-tree U, but this is only asserted in the sentence 'It is easy to see that there is a natural embedding of all G_t to some U_s...'. This assertion is load-bearing because the color of a new vertex is defined as c(inj_{G_t}(v_t)). Please provide an explicit induction: after t steps, every online k-tree G_t embeds into U_{t+1} extending the embedding of G_{t-1}; when v_t is joined to a k-clique C of previous vertices, map v_t to the vertex that U_{t+1} adds for the image of C, and verify that this vertex is fresh because U_{t+1} contains all earlier images and each k-clique gets exactly one new vertex in the construction. The base case G_0 should also be handled explicitly.","section":"Section 2, proof of Theorem 1.2"},{"comment":"The universality of O for online paths is stated as 'it is easy to see that O is indeed a universal graph of online paths' and the proof is left to the reader. This universality is as load-bearing here as the analogous statement in Theorem 1.2, and the edge-deletion operation makes the required embedding slightly different from the k-tree case because G_t is not necessarily a superset of G_{t-1}. Please give the injection construction by induction on t, specifying how the new vertex is mapped when it is appended at an end or when it subdivides an edge, and verify that the image of every G_t is a subgraph of O even after deletions.","section":"Section 2, proof of Theorem 1.5"},{"comment":"The reduction from online partial k-trees to online k-trees is asserted in one sentence: 'we can always suppose that C_t = ∅, i.e., we do not delete edges, and also we can suppose that |D_t| = min(k, |V_{t-1}|)'. To make Corollary 1.3 fully justified, prove that every online sequence of partial k-tree updates can be completed online by adding extra edges so that each G_t is a subgraph of a k-tree T_t with T_{t-1} ⊆ T_t. In particular, when v_t arrives with a neighbor set S of size at most k that is a clique, argue that in a k-tree T_{t-1} every clique is contained in some k-clique, so v_t can be attached to a k-clique containing S; also explain why a nonrepetitive coloring of the completion restricts to a nonrepetitive coloring of the original graph.","section":"Section 1.1, Corollary 1.3"}],"minor_comments":[{"comment":"The phrase 'the pending edges form a path' should presumably read 'the new edges form a path', since 'pending' is not defined in the construction.","section":"Section 2, proof of Theorem 1.5"},{"comment":"In Definition 2.2, 'directed paths in T' should be 'directed paths in G', because the graph under discussion is G, not T.","section":"Section 2, Definition 2.2"},{"comment":"In reference [1], 'Ha/suppress luszczak' appears to be an OCR corruption of 'Hałuszczak'; the correct name should be restored.","section":"References"},{"comment":"The compactness step using König's lemma is standard, but the details could be written out for self-containedness: the finite colorings of the nested U_i form a finitely branching tree, an infinite branch yields a coloring of U, and every finite path of U lies in some U_i and is therefore nonrepetitively colored.","section":"Section 2, proof of Theorem 1.2"}],"recommendation":"major_revision","confidential_remarks":"This is a short and clean note. The main result appears mathematically correct, and the relationship to simultaneous work [6] is acknowledged honestly. My recommendation of major revision is driven entirely by the need to supply the missing proofs of the universality embeddings and the partial k-tree completion; once those are added, the paper should be acceptable. There are no concerns about novelty or attribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know upfront: this is a real result, and it's correct. Keszegh and Zhu show that every graph of tree-width k can be colored online nonrepetitively with 4^k colors, matching the offline bound from Kündgen and Pelsmajer. That closes the natural online/offline gap for bounded tree-width, and it is the first time the online model has been handled for this class beyond paths.\n\nWhat's actually new: the universal k-tree construction and the compactness argument that lift the offline bound to an infinite universal graph, then pull it back to any online sequence. The 4^k theorem for k-trees, and the corollaries for partial k-trees, trees, cycles, and series-parallel graphs, are new. The path result (12 colors) was proved independently and simultaneously by Grytczuk, Szafruga, and Zmarz; the authors say so and include the proof for completeness. That is honest and does not inflate novelty.\n\nThe reader's report flags three sketched steps: the universality of U, the Kőnig's lemma passage, and the partial-k-tree completion. I read those paragraphs too, and I agree they are terse. But I also checked them, and they are routine. The embedding into U is inductive: after t steps the current k-tree embeds into U_{t+1}, and a new vertex joined to a k-clique maps to the vertex U adds for that clique's image. For partial k-trees you complete to a k-tree on the fly; the same embedding works. Compactness via Kőnig's lemma is standard for finitely branching trees of finite colorings. None of this is circular, as the stress-test note also concludes. The paper leans on the offline result of [8], which is the right thing to lean on.\n\nSoft spots, in proportion: the exposition is thinner than ideal—three 'easy to see' or 'left to the reader' moments in a paper whose entire point is one reduction. A referee should ask the authors to write those out, especially the path-universality embedding in Theorem 1.5, which involves edge deletions. The last section on list-colorings is explicitly preliminary and raises open problems; it doesn't weaken the main theorems but it also doesn't add much.\n\nWho is this for: anyone working on nonrepetitive colorings, online graph coloring, or tree-width methods. It is a clean, short result that deserves a place in the literature. The citation pattern looks fair: simultaneous work is acknowledged, and the offline bound is properly attributed.\n\nRecommendation: yes, send it to peer review. It is a small but solid paper; the referee should request expanded proofs of the embedding and compactness steps, but there is no correctness risk in the main claim.","headline":"A short, sound paper that settles online nonrepetitive coloring for bounded tree-width graphs with the same 4^k colors as offline; the proof is correct, though the exposition is terser than it should be.","tokens_in":7061,"tokens_out":1971,"would_cite":true,"duration_ms":18809,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"4^k colors suffice online for every k-tree.","keywords":["online nonrepetitive coloring","k-trees","partial k-trees","tree-width","universal graph","nonrepetitive sequences","outerplanar graphs","list-coloring"],"falsifier":"For k=2, enumerate all finite online 2-trees and check the claimed embedding into U: if some sequence of arrivals makes a new vertex attach to two earlier vertices whose images in U are not a 2-clique at the corresponding stage, the universal embedding fails and the 4^k online coloring scheme has no well-defined rule for that step.","tokens_in":6078,"feed_emoji":"🎨","tokens_out":6193,"duration_ms":54267,"temperature":0.7,"pith_summary":"The paper proves that a graph whose vertices arrive one at a time can still be colored online nonrepetitively with 4^k colors whenever the final graph is a k-tree. The same number of colors works for every partial k-tree, that is, every graph of tree-width at most k, and this immediately gives 16 colors for online trees, cycles, and series-parallel graphs. The proof works by transferring an offline coloring of one infinite universal k-tree to every finite online k-tree through order-preserving embeddings. If the argument is correct, the online version of bounded-tree-width nonrepetitive coloring is settled with exactly the same color count as the offline version.","feed_headline":"4^k colors suffice online for every k-tree.","feed_subtitle":"Even when vertices arrive one by one and must be colored instantly, bounded-tree-width graphs stay nonrepetitively 4^k-colorable.","key_machinery":"The central object is the universal k-tree U: U_1 = K_{k+1} and U_{i+1} adds, for each k-clique of U_i, a new vertex joined to exactly that clique. It carries the argument because it contains every finite online k-tree as an incremental subgraph embedding, and because being a k-tree makes U eligible for the offline 4^k-coloring theorem. The transfer step c'(v_i) = c(inj(v_i)) turns a static coloring of U into a valid online coloring rule.","core_discovery":"The central claim is that online nonrepetitive coloring of k-trees costs no extra colors over the offline case. An infinite universal k-tree U is built by starting with K_{k+1} and, recursively, adding a new vertex to every k-clique of the current graph. Every finite online k-tree G_t can be injected into some finite stage of U so that the injection extends as new vertices arrive; an offline nonrepetitive 4^k-coloring of U, obtained from the known bounded-tree-width result and a standard compactness argument, then colors each arriving vertex by the image of its injection. Because paths of G_t map to paths of U, this coloring is nonrepetitive at every step.","pith_inferences":["A natural test is to simulate the universal-graph embedding for k=2 with adversarial arrival sequences; if the embedding ever fails, the 4^k bound collapses, while successful simulation would support extending the transfer method to other hereditary graph classes.","The paper leaves open whether any constant number of list colors suffices for online nonrepetitive coloring of paths or k-trees; if such a constant fails to exist, online constraints would create a genuine separation from the offline list-coloring world.","The vertical and directed nonrepetitive colorings introduced for the path proof could be studied independently, since an improved vertically nonrepetitive coloring of the universal path graph would directly lower the 12-color path bound."],"forward_implications":["Every partial k-tree, hence every graph of tree-width at most k, is online nonrepetitively 4^k-colorable.","Online trees, cycles, and series-parallel graphs are all online nonrepetitively 16-colorable.","Online paths are online nonrepetitively 12-colorable, improving the general bound for that special case.","No online adversary can force more than 4^k colors on a k-tree, since the offline coloring of the universal graph already blocks every possible repetitive path."],"supporting_citations":[{"why":"Supplies the offline nonrepetitive 4^k-coloring of bounded-tree-width graphs, the bound that is transferred to the universal k-tree.","marker":"[8]"},{"why":"Introduces the existence of an infinite nonrepetitive sequence over three symbols, the starting point of the whole problem.","marker":"[9]"},{"why":"Introduces the graph version of nonrepetitive colorings and the associated chromatic number used throughout.","marker":"[1]"},{"why":"Independent proof that online paths can be colored with 12 colors, providing context for the path result.","marker":"[6]"},{"why":"Supplies the vertically nonrepetitive list-coloring lemma used to show that left-to-right online paths are list-colorable with lists of size 4.","marker":"[7]"}],"fun_headline_variants":["Online nonrepetitive coloring of k-trees: 4^k colors always suffice","No extra colors online: k-trees stay 4^k-colorable nonrepetitively","4^k colors for online k-trees, matching offline bound","Even adversarially arriving vertices keep k-trees 4^k-colorable","Nonrepetitive online coloring: 4^k colors handle any k-tree"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the assertion that every finite online k-tree embeds incrementally into the universal k-tree U; if some arrival sequence produced a graph that cannot be embedded this way, the coloring rule c'(v_i)=c(inj(v_i)) would not be well-defined and the 4^k bound would not follow from this argument.","fun_headline_variants_meta":{"raw":{"variants":["Online nonrepetitive coloring of k-trees: 4^k colors always suffice","No extra colors online: k-trees stay 4^k-colorable nonrepetitively","4^k colors for online k-trees, matching offline bound","Even adversarially arriving vertices keep k-trees 4^k-colorable","Nonrepetitive online coloring: 4^k colors handle any k-tree"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000828,"raw_usage":{"total_tokens":3523,"prompt_tokens":752,"completion_tokens":2771,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":368,"completion_tokens_details":{"reasoning_tokens":2667}},"tokens_in":368,"tokens_out":2771,"duration_ms":20340,"temperature":1.0,"reasoning_tokens":2667,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:46:53.710431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For k=2, enumerate all finite online 2-trees and check the claimed embedding into U: if some sequence of arrivals makes a new vertex attach to two earlier vertices whose images in U are not a 2-clique at the corresponding stage, the universal embedding fails and the 4^k online coloring scheme has no well-defined rule for that step.","supporting_citations":[{"cited_title":"K ¨undgen, M","cited_arxiv_id":null,"evidence_quote":"Supplies the offline nonrepetitive 4^k-coloring of bounded-tree-width graphs, the bound that is transferred to the universal k-tree."},{"cited_title":"Thue, ¨Uber unendliche Zahlenreihen, Norske Vid Selsk Skr I Mat Nat Kl Christiana 7 (1906), 1–22","cited_arxiv_id":null,"evidence_quote":"Introduces the existence of an infinite nonrepetitive sequence over three symbols, the starting point of the whole problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the graph version of nonrepetitive colorings and the associated chromatic number used throughout."},{"cited_title":"Grytczuk, P","cited_arxiv_id":null,"evidence_quote":"Independent proof that online paths can be colored with 12 colors, providing context for the path result."},{"cited_title":"Micek Nonrepetitive choice number of trees, SIAM J","cited_arxiv_id":null,"evidence_quote":"Supplies the vertically nonrepetitive list-coloring lemma used to show that left-to-right online paths are list-colorable with lists of size 4."}],"review_version":1}