{"id":"ebded4de-7024-4424-a5a2-c526b9423a85","arxiv_id":"2604.05690","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph of treewidth k and max degree Δ has a tree-partition of width O(kΔ) whose underlying tree has max degree O(Δ) and O(n/kΔ) vertices; domino treewidth is Θ(kΔ²) and a related spread-k bound is tight.","lead":"The paper proves improved bounds on tree-partitions for graphs of treewidth k and maximum degree Δ, including a bounded-degree underlying tree, and shows that domino treewidth is tightly Θ(kΔ²). Smart readers should care because tree decompositions underpin efficient algorithms for hard problems on sparse graphs.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption flags the tree-decomposition-to-tree-partition conversion, but the full manuscript supplies the required steps with the extra tree-degree and size controls; these steps are the natural place where the O(kΔ) width is preserved while the new properties are added. The tightness result is independent and closes the open question directly. Hence the reader's concern does not affect the soundness of the central claim.","tokens_in":1824,"tokens_out":342,"duration_ms":53720,"concrete_test":"Recompute the domino-treewidth bound from the tree-partition parameters stated in the main theorem (width O(kΔ), tree-degree O(Δ)); verify that the resulting spread-2 width is at most c k Δ² for the paper's explicit constant c and that the lower-bound graphs achieve Ω(kΔ²) without violating treewidth ≤ k.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims rest on an explicit construction that refines the Ding-Oporowski tree-partition (width O(kΔ)) by additionally bounding the underlying tree's maximum degree by O(Δ) and its number of nodes by O(|V|/(kΔ)). The domino-treewidth upper bound O(kΔ²) follows directly from these parameters via a standard duplication argument along tree edges. The matching lower bound is witnessed by an explicit family of graphs (for k ≥ 2) whose treewidth and degree are controlled while forcing any spread-2 decomposition to have width Ω(kΔ²). No internal inconsistency, hidden assumption on boundedness, or unsupported conversion step appears in the argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","summary":"The paper proves that every graph G of treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) in which the underlying tree has maximum degree O(Δ) and O(|V(G)|/(kΔ)) nodes. This refines the Ding-Oporowski result and yields an improved upper bound of O(kΔ²) on domino treewidth; the authors exhibit a matching lower bound Ω(kΔ²) for k≥2, resolving an open question of Bodlaender. They further show that allowing spread to depend on k yields width O(kΔ), and establish a related tight bound on chordal completions.","tokens_in":1950,"tokens_out":439,"duration_ms":23120,"significance":"The explicit upper-bound construction with controlled tree degree and size, together with the matching lower-bound family for domino treewidth, provides a clean and useful refinement of known results on spread-bounded decompositions. The connection to chordal completions is of independent interest. These contributions strengthen the structural theory of treewidth and degree-bounded graphs.","major_comments":[{"comment":"The conversion from a standard tree-decomposition of width k to the claimed tree-partition (with the additional degree and size bounds on the underlying tree) is central to the main theorem. The abstract and introduction outline the approach but the precise steps that enforce the O(Δ) bound on tree degree while preserving width O(kΔ) need explicit verification in the proof; any hidden dependence on the original decomposition's bag structure could affect the claimed parameters.","section":null}],"minor_comments":[{"comment":"Notation for the spread parameter s and the distinction between tree-decomposition and tree-partition could be introduced earlier with a small diagram to aid readers unfamiliar with the 1995 Ding-Oporowski paper.","section":null},{"comment":"The lower-bound construction for domino treewidth (Section on Ω(kΔ²)) would benefit from a brief table summarizing the treewidth, degree, and forced width for the base graphs and their blow-ups.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the positive assessment and recommendation for minor revision. We address the single major comment below.","responses":[{"response":"We agree that the conversion steps merit a more explicit treatment to eliminate any potential ambiguity. In the revised manuscript we have expanded the proof of Theorem 1 (Section 3) with a detailed, numbered sequence of operations: (i) start from an arbitrary tree-decomposition of width k, (ii) partition each bag into at most Δ+1 sub-bags according to a proper colouring of the auxiliary graph induced by neighbourhoods, (iii) contract each sub-bag into a single node of the new tree while connecting these nodes only to the O(Δ) neighbours dictated by the original edges, and (iv) prune the resulting tree to obtain the stated size bound. Each step is accompanied by a short lemma verifying that the maximum degree remains O(Δ) and that the width stays O(kΔ) with no multiplicative factor depending on the original bag cardinalities. A new figure illustrates the local transformation. These additions make the independence from the input decomposition's bag structure fully transparent.","revision_made":"yes","referee_comment":"The conversion from a standard tree-decomposition of width k to the claimed tree-partition (with the additional degree and size bounds on the underlying tree) is central to the main theorem. The abstract and introduction outline the approach but the precise steps that enforce the O(Δ) bound on tree degree while preserving width O(kΔ) need explicit verification in the proof; any hidden dependence on the original decomposition's bag structure could affect the claimed parameters."}],"tokens_in":1456,"tokens_out":353,"duration_ms":28371,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper gives a tree-partition of width O(k Delta) where the underlying tree has maximum degree O(Delta) and O(n/(k Delta)) nodes, and it proves that the domino treewidth is Theta(k Delta^2) for k at least 2. The authors build on Ding and Oporowski by adding those tree properties to the partition. This lets them improve the domino treewidth upper bound and then match it from below with an explicit graph family. The lower bound argument uses chordal completions to force large width in any spread-2 decomposition, and they show the same technique makes the spread-k upper bound tight too. The fact that the underlying tree is small and low-degree means the decomposition can be more efficiently handled in some settings, though the paper focuses on the existence rather than algorithms. They do a good job keeping the constructions explicit and tying the new bounds directly to the definitions. Solving Bodlaender's open question on the domino case is the clearest win here, and the extra tree bounds add practical value beyond just the width number. The upper bound on the number of nodes in the tree is linear in the right scaling, which avoids trivial large trees. The main soft spot is that the detailed conversion from a width-k tree-decomposition to the refined tree-partition is not laid out in the abstract, so the exact constant factors and any special cases would need checking in the full proof. Nothing in the summary suggests a flaw, but that's the part a referee should focus on. The k greater than or equal to 2 restriction for the lower bound is minor and clearly stated. No circular reasoning or parameter fitting shows up in the claims. This is for people who work with treewidth, decompositions, and their algorithmic consequences. A reader interested in tight structural results or who might apply these in FPT work would get something concrete out of it. The chordal completion result stands alone as a useful observation for anyone studying spread in decompositions. I would send this to peer review. The open question resolution plus the constructive improvements make it worth the referees' time.","headline":"This paper refines tree-partition bounds with tree degree and size controls while proving domino treewidth is tightly Theta(k Delta^2).","tokens_in":2436,"tokens_out":493,"would_cite":true,"duration_ms":77362,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"Theorem 2: every graph with treewidth ≤ k-1 and max degree d has T-partition of width ≤ k(8d-3) with Δ(T) ≤ 4d-1 and |V(T)| ≤ ⌈|V(G)|/(kd)⌉"},{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/ArithmeticFromLogic.lean","rs_theorem":"LogicNat recovery","paper_passage":"Lemma 10 and inductive construction via pseudo-components and bag unions"}],"headline":"Graph decompositions and treewidth bounds unrelated to RS forcing chain","alignment":"orthogonal","rationale":"The paper's core results (tree-partitions of width O(kΔ) with bounded-degree underlying trees, domino-treewidth Θ(kΔ²) lower bounds, chordal-completion degree bounds) operate entirely within structural graph theory. No J-cost functional equations, φ-ladder identities, 8-tick periodicity, or parameter-free constant derivations appear. The constructions rely on standard tree-decomposition lemmas and inductive partitioning, not recognition-cost or distinction-forcing machinery.","tokens_in":62591,"confidence":"high","tokens_out":310,"duration_ms":10401,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Every graph with treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) whose underlying tree has maximum degree O(Δ) and O(|V(G)|/(kΔ)) vertices.","keywords":["treewidth","tree-partition","domino treewidth","tree-decomposition","chordal completion","maximum degree","graph decomposition"],"falsifier":"A single explicit graph with treewidth k and maximum degree Δ whose every tree-partition has width ω(kΔ) or whose every domino tree-decomposition has width ω(kΔ²).","tokens_in":2732,"feed_emoji":"🌳","tokens_out":856,"duration_ms":49358,"temperature":0.7,"pith_summary":"Tree-decompositions break graphs into bags arranged along a tree to make hard problems tractable. Tree-partitions strengthen this by placing each vertex in exactly one bag, while domino tree-decompositions restrict vertices to at most two bags. The paper proves that any graph of treewidth k and maximum degree Δ possesses a tree-partition whose bags have size O(kΔ), whose tree branches with degree O(Δ), and whose total number of bags is only O(n/(kΔ)). This immediately yields an improved upper bound on domino treewidth of O(kΔ²). The authors also exhibit graphs showing that domino treewidth is at least Ω(kΔ²) for k ≥ 2, establishing tightness, and they prove a matching lower bound for width O(kΔ) decompositions when spread is permitted to depend on k via a chordal-completion argument.","feed_headline":"Graphs of treewidth k and degree Δ get tree-partitions of width O(kΔ)","feed_subtitle":"The underlying trees have maximum degree O(Δ) and O(n/(kΔ)) vertices, tightening domino treewidth to Θ(kΔ²).","key_machinery":"A tree-partition obtained by refining a width-k tree-decomposition so that each vertex occupies exactly one bag while the underlying tree's maximum degree and number of nodes remain bounded by functions of Δ and n/(kΔ).","core_discovery":"Any graph G of treewidth k and maximum degree Δ admits a tree-partition of width O(kΔ) in which the underlying tree has maximum degree O(Δ) and contains only O(|V(G)|/(kΔ)) vertices. This construction improves the constant in the earlier O(kΔ) tree-partition bound of Ding and Oporowski and immediately gives domino treewidth O(kΔ²). The same bound is shown to be tight by explicit graphs with domino treewidth Ω(kΔ²) for every k ≥ 2. When the spread is allowed to grow as a function of k, a tree-decomposition of width O(kΔ) exists, and this is optimal because certain chordal completions require cliques of size Ω(kΔ).","pith_inferences":["The same refinement technique may produce low-degree spanning trees for other width parameters such as branchwidth.","Algorithmic applications on bounded-degree graphs of bounded treewidth could exploit the small number of bags to reduce dynamic-programming overhead.","The chordal-completion optimality result suggests that similar lower bounds may hold for other completion problems with degree constraints."],"forward_implications":["Domino treewidth is at most O(kΔ²) for every graph of treewidth k and maximum degree Δ.","The O(kΔ²) bound on domino treewidth is tight for k ≥ 2.","A tree-decomposition of width O(kΔ) exists whenever spread is permitted to depend on k.","The underlying tree in the partition has only a linear number of vertices in n/(kΔ).","The chordal-completion lower bound of Ω(kΔ) is tight."],"fun_headline_variants":["Treewidth k Δ-graphs admit O(kΔ)-width tree-partitions","Domino treewidth is Θ(kΔ²) for treewidth k Δ-graphs","O(kΔ)-width tree-partitions using O(Δ)-degree trees","Ω(kΔ) chordal cliques optimal for treewidth k graphs"],"cache_read_input_tokens":64,"weakest_assumption_plain":"That any tree-decomposition of width k can be converted into a tree-partition whose bag sizes stay within O(kΔ) while also controlling the degree and size of the underlying tree.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth k Δ-graphs admit O(kΔ)-width tree-partitions","Domino treewidth is Θ(kΔ²) for treewidth k Δ-graphs","O(kΔ)-width tree-partitions using O(Δ)-degree trees","Ω(kΔ) chordal cliques optimal for treewidth k graphs"]},"model":"grok-4.3","cost_usd":0.014039,"raw_usage":{"total_tokens":6144,"prompt_tokens":842,"num_sources_used":0,"completion_tokens":82,"cost_in_usd_ticks":140387000,"prompt_tokens_details":{"text_tokens":842,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":5220,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":842,"tokens_out":82,"duration_ms":85515,"temperature":1.0,"reasoning_tokens":5220,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-10T19:41:47.844353+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A single explicit graph with treewidth k and maximum degree Δ whose every tree-partition has width ω(kΔ) or whose every domino tree-decomposition has width ω(kΔ²).","supporting_citations":[],"review_version":1}