REVIEW 3 major objections 4 minor 9 references
A note about online nonrepetitive coloring $k$-trees
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 4^k colors suffice online for every k-tree.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 2, proof of Theorem 1.2] 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 2, proof of Theorem 1.5] 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 1.1, Corollary 1.3] 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.
minor comments (4)
- [Section 2, proof of Theorem 1.5] 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 2, Definition 2.2] In Definition 2.2, 'directed paths in T' should be 'directed paths in G', because the graph under discussion is G, not T.
- [References] In reference [1], 'Ha/suppress luszczak' appears to be an OCR corruption of 'Hałuszczak'; the correct name should be restored.
- [Section 2, proof of Theorem 1.2] 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.
Circularity Check
No circularity: the 4^k online bound is derived from the independent offline theorem of Kündgen and Pelsmajer via a genuinely universal k-tree construction; no target result is assumed.
full rationale
Theorem 1.2 follows a two-part structure that is not circular. First, the paper constructs an infinite universal k-tree U as the nested union U1 ⊂ U2 ⊂ ... where Ui+1 adds a new vertex for every k-clique of Ui. Each Ui is a finite k-tree, so the independent theorem of Kündgen and Pelsmajer [8] gives a nonrepetitive 4^k-coloring of Ui; König's Lemma then yields a nonrepetitive coloring of U. Second, the paper argues that every online k-tree Gt embeds incrementally into U, and defines c'(vi) = c(inj(vi)). This is a genuine transfer argument: the offline result [8] is external and does not presuppose the online theorem, and the universal graph construction is independent of the coloring result. The assertion that every online k-tree embeds into U is stated tersely ('It is easy to see that there is a natural embedding of all Gt to some Us'), but it is a standalone combinatorial claim about k-tree completion, not an assumption of the theorem's conclusion. Corollary 1.3 reduces partial k-trees to k-trees by completing the partial graph at each step; this is a standard monotonicity argument, and the online coloring of the completed k-tree restricts to the partial graph. Theorem 1.5 likewise builds a universal outerplanar graph O and appeals to the independent [8] result that outerplanar graphs admit nonrepetitive 12-colorings; the universality proof is left to the reader, but this is an omitted exposition detail rather than a circular step. The only self-citation is reference [4], which includes Xuding Zhu, but it is used only to state that trees in general do not have bounded nonrepetitive choice number, which is not load-bearing for the main results. No fitted parameter is renamed as a prediction, and no definition presupposes the target bound. The paper is self-contained relative to independent external benchmarks, so the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (4)
- domain assumption Offline bound of Kündgen and Pelsmajer [8]: graphs of tree-width at most k, in particular k-trees, are nonrepetitively 4^k-colorable; the paper also uses their 12-color bound for outerplanar graphs in Theorem 1.5.
- standard math Kőnig's lemma / compactness: if every finite induced subgraph of a countable graph has a nonrepetitive q-coloring, then the infinite graph has one.
- domain assumption Every partial k-tree is a subgraph of a k-tree, and every clique of size at most k in a k-tree is contained in a k-clique, so online partial k-tree processes can be completed by adding edges and ignoring deletions.
- domain assumption Trees, cycles, and series-parallel graphs are online partial 2-trees under the definitions in Definition 1.1.
Cite this review
Pith. "Pith review of A note about online nonrepetitive coloring $k$-trees." pith.science (2026). https://pith.science/paper/PQY5JYW3
@misc{pith2026190902612,
author = {Pith},
title = {Pith review of: A note about online nonrepetitive coloring $k$-trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/PQY5JYW3}},
note = {Machine review of arXiv:1909.02612}
}
abstract
We prove that it is always possible to color online nonrepetitively any (partial) $k$-tree (that is, graphs with tree-width at most $k$) with $4^k$ colors. This implies that it is always possible to color online nonrepetitively cycles, trees and series-parallel graphs with $16$ colors. Our results generalize the respective (offline) nonrepetitive coloring results.
Figures
Reference graph
Works this paper leans on
-
[8]
A. K ¨undgen, M. Pelsmajer , Nonrepetitive colorings of graphs of bounded tree- width. Discrete Math, 308 (2008) 4473–4478
work page 2008
-
[1]
N. Alon, J. Grytczuk, M. Ha/suppress luszczak, O. Riordan, Nonrepetitive colorings of graphs, Random Struct. Alg. 21 (2002), 336–346
work page 2002
-
[2]
K.Chen, A. Fiat, H. Kaplan, M. Levy, J. Matou ˇsek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, E. Welzl. Online conflict-free coloring for intervals, SIAM Journal on Computing, 36(5) (2007), 1342–1359
work page 2007
-
[3]
Planar graphs have bounded nonrepetitive chromatic number
V. Dujmovi´c, L. Esperet, G. Joret, B. Walczak, D. R. Wood Planar graphs have bounded nonrepetitive chromatic number, https://arxiv.org /abs/1904.05269
work page Pith review arXiv 1904
-
[4]
F. Fiorenzi, P. Ochem, P. Ossona de Mendez, X. Zhu Thue choosability of trees, Discrete Applied Mathematics 159 (2011), 2045–2049
work page 2011
-
[5]
Grytczuk, Nonrepetitive Colorings of Graphs - A Survey, Int
J. Grytczuk, Nonrepetitive Colorings of Graphs - A Survey, Int. J. Math. Math . Sci. 2007, Art. ID 74639, 10 pp
work page 2007
-
[6]
J. Grytczuk, P. Szafruga, M. Zmarz Online version of the theorem of Thue, Information Processing Letters 113(5-6) (2013), 193-195
work page 2013
-
[7]
Micek Nonrepetitive choice number of trees, SIAM J
J Kozik, P. Micek Nonrepetitive choice number of trees, SIAM J. Discrete Math. 27(1) (2013), 436–446
work page 2013
Show all 9 references
-
[9]
Thue, ¨Uber unendliche Zahlenreihen, Norske Vid Selsk Skr I Mat Nat Kl Christiana 7 (1906), 1–22
A. Thue, ¨Uber unendliche Zahlenreihen, Norske Vid Selsk Skr I Mat Nat Kl Christiana 7 (1906), 1–22. 8
1906
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.