{"id":"4aed6559-e848-47a1-8020-b8bebc42541e","arxiv_id":"2507.03163","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-vertex planar graph can be 3-coloured so that each monochromatic connected component has at most O(n^{4/9}) vertices, improving the previous O(n^{1/2}) bound.","lead":"This paper improves the best known bound for 3-colouring planar graphs with small monochromatic components, from O(n^{1/2}) to O(n^{4/9}). The proof introduces a face-weighted separator technique that controls both separator size and the treewidth of the separator's induced subgraph.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 10's bound |X_C| ≤ log_{3/2}N divides by N_C; zero-weight high-treewidth components are not excluded, so the separator-size accounting is unsupported.","rationale":"The reader's verdict CONDITIONAL is appropriate: the theorem is plausible and many parts are careful, but the main lemma has a gap that is not merely arithmetic. The concern is not that N_C=0 is impossible; it is that the proof never rules it out and even the lemma's own hypotheses admit such components. The proposed grid construction shows the disputed inference is not valid as a logical step. If the authors add an argument bounding zero-weight branches (e.g., by charging holes to |S| instead of N_C, or by choosing nooses that also balance hole counts), the O(n^{4/9}) result may survive. Because the issue is in the load-bearing Lemma 10 and the final bound depends on it, the paper should not be accepted without a fix; CONDITIONAL (or revised) remains the right call.","tokens_in":13763,"tokens_out":43062,"duration_ms":527096,"concrete_test":"Construct the instance above: G is a k×k grid with one extra vertex inside each cell joined to its four corners; assign weight 1/4 to each triangular face inside every cell, W=1, N=k^2; put all inner vertices in S. Check that the component C=G−S has N_C=0, |X_C|=k^2, every vertex of C incident to an X_C face, and tw(C)=k ≥ 12√(10 log_{3/2}N +36)+7. Then verify whether Lemma 10's iterative noose procedure can reach this C as a processed component (e.g., by cutting the cells one by one). If it can, the line '|X_C| ≤ log_{3/2}N' is contradicted and the separator-size sum in Lemma 10 has no valid bound for this branch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is in Lemma 10: after proving N_C ≤ (2/3)^{|X_C|}N, the paper concludes |X_C| ≤ log_{3/2}(N/N_C) ≤ log_{3/2}N. This requires N_C > 0. The paper gives no argument that N_C > 0 for every processed component. A component with N_C = 0 is compatible with all stated hypotheses: take the k×k grid with an extra vertex inside every cell, all triangular cell-faces weighted so that W=1 and N=k^2, and put the k^2 inner vertices into S. The remaining component C is the grid; every face of C is a non-original hole, so X_C has k^2 faces and N_C=0, and each vertex of C is incident to a hole, exactly the case Lemma 6 allows. For k = 12√(10 log_{3/2}N +36)+7, tw(C)=k ≥ t while log_{3/2}N ≈ 2 log_{3/2}k, so |X_C|=k^2 ≫ log_{3/2}N. Thus the inference is false without a positivity argument. This matters because (3), N_C/W ≥ 36 + 9|X_C|, and the subsequent bound |C_i| ≤ 160N/(W(t−7)^2)(3/4)^i use this log bound to charge the hole count against face weight; if N_C=0 there is no such charge, and the total |S| estimate no longer follows. The reader's 'at most one new face' concern is real but secondary: even granting |X_{C'}|≤|X_C|+1, the induction still fails at the division by N_C.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every n-vertex planar graph admits a 3-colouring in which every monochromatic component has O(n^{4/9}) vertices, improving the previous O(n^{1/2}) upper bound of Linial, Matoušek, Sheffet, and Tardos. The proof develops separator and treewidth tools for planar graphs: Lemma 5 gives a q-separator whose induced subgraph has small treewidth; Lemmas 6--9 give weighted noose and cycle separators with explicit constants; Lemma 10 iterates these to remove a set S with |S| = O((N/W)t^{-1} + (N/W)t^{-2}) and tw(G-S) < t; Theorem 11 combines Lemma 10 with a separator lemma of Dvořák and Wood to obtain the final clustered 3-colouring. The paper is self-contained apart from standard external theorems and includes explicit, though non-optimised, constants.","tokens_in":14099,"tokens_out":30624,"duration_ms":331326,"significance":"If the main theorem is correct, it is a genuine advance on a well-known open problem in clustered colouring, and the separator/treewidth lemmas (especially Lemmas 5 and 6) are of independent interest. The proof strategy is natural and the auxiliary lemmas are mostly well argued; the paper also clearly identifies the previous lower bound and the gap that remains. However, the central engine, Lemma 10, has a serious gap concerning components with zero face-weight, and a separate inequality error in the bucketing argument. As written, the proof of the main theorem is not complete. The errors appear local enough that the asymptotic result may be repairable, but substantial work is needed in Lemma 10.","major_comments":[{"comment":"The final geometric sum is evaluated incorrectly. With c = 3√2, the displayed series equals c · √(3/2) / (√(3/2) − 1) = 9√2 + 6√3 ≈ 23.12, not < 12. Consequently the stated bound |S| ≤ 12n/q^{1/2} is not justified, and the subsequent numerical claims in Lemma 5 and Theorem 11 (e.g., |S0| ≤ 3n^{7/9} and the constant 16 in the clustering bound) are not established with the displayed constants. The asymptotic O(n^{4/9}) conclusion would survive if all constants are enlarged, but the explicit-constant statements need correction.","section":"Lemma 4"},{"comment":"The inference |X_C| ≤ log_{3/2}(N/N_C) ≤ log_{3/2}N divides by N_C and therefore requires N_C > 0. The proof never establishes N_C > 0 for every processed component. A component C with N_C = 0 is compatible with the stated hypotheses: for instance, take a large grid component whose faces are all non-original holes, with the original face-weighting assigned to removed vertices. In such a case Lemma 6 gives no contradiction, and the later inequality (3), N_C/W ≥ 36 + 9|X_C|, cannot hold. Since (3) and the subsequent bucket estimates control the total separator size, the central bound is unsupported without an additional argument excluding or otherwise handling zero-weight components. The concern raised in the reader's report about |X_{C'}| ≤ |X_C| + 1 is secondary; even granting that bound, the log estimate fails when N_C = 0.","section":"Lemma 10, after Eq. (2)"},{"comment":"The level-monotonicity claim is reversed. From (3) the proof obtains M_C > (4/3)M_{C'} for a child C′, where M_C = |X_C| + N_C/W. For C ∈ C_i, M_C < A(4/3)^{i+1} with A = (t−7)^2/144, so M_{C′} < A(4/3)^i; hence C′ lies in C_j with j ≤ i−1, not j ≥ i+1 as stated. The conclusion that distinct C,D ∈ C_i satisfy F(C) ∩ F(D) ∩ F(G) = ∅ is therefore not obtained by the argument given, even though it may be recoverable from the opposite inequality. This is load-bearing because the bound |C_i| ≤ 160N/(W(t−7)^2)(3/4)^i relies on the claimed disjointness.","section":"Lemma 10, bucketing after Eq. (3)"}],"minor_comments":[{"comment":"In the sentence 'any component C of G−V(λ) is contained in some component C′ of G−V(λ)', the second graph should be G′−V(λ).","section":"Lemma 9"},{"comment":"The inequality |V(G2)|(k+1) ≤ |S|t is not valid for non-integer t, since k+1 can equal t+1. The application of Lemma 2 can be repaired by using k+1 ≤ t+1 and the fact that the estimate holds for sufficiently large n, but the displayed inequality should be corrected.","section":"Theorem 11"},{"comment":"The collection of processed components and a generic component are both denoted by C, which makes the paragraph after (2) hard to read; using a different symbol for the collection would improve clarity.","section":"Lemma 10"},{"comment":"The phrase 'Each level 1 component has more than q vertices' is only true for components that are actually separated; the level definition could be phrased more explicitly to avoid confusion.","section":"Lemma 4"}],"recommendation":"major_revision","confidential_remarks":"The paper is on an important problem and the high-level strategy is appealing, but Lemma 10 is the engine of the paper and its proof currently has a serious gap (the N_C = 0 case) and an incorrect inequality in the main accounting. I recommend major revision. The authors should be asked to repair Lemma 10; if the zero-weight case cannot be resolved, the main theorem may not follow from the present approach. The constant error in Lemma 4 is comparatively minor and can be fixed by recomputing constants. No circularity concern: Lemma 2 is from the authors' prior work but is a standard separator-treewidth statement, and the central proof is otherwise self-contained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline is that this paper gives a real improvement on the clustered 3-colouring bound for planar graphs, from O(n^{1/2}) to O(n^{4/9}), and the face-weighting separator machinery is honest work. But the central proof step in Lemma 10 has a gap that is not a typo. The paper assumes you can go from N_C ≤ (2/3)^{|X_C|}N to |X_C| ≤ log_{3/2}N, which requires N_C > 0. That positivity is never established, and the hypotheses allow N_C=0. Take a grid, put an extra vertex inside every cell so it becomes a triangulation with the grid edges intact, then move all those extra vertices into the separator S. The remaining component is the grid; every one of its faces is a hole, so N_C=0 and |X_C| is the number of cells, which is about k^2, while log_{3/2}N is about 2 log k. The inference fails. This matters because (3) and the bound on |C_i| use that log bound to charge holes against face weight.\n\nThe rest of the paper holds up better. Lemma 5, giving a q-separator whose induced subgraph has small grid minor, is a good observation and the proof is clean. Lemma 4's constant is off: the geometric sum evaluates to about 23.1, not 12, but that only changes constants. The citation pattern looks fine; the prior bound from Linial et al. is correctly credited.\n\nSo where does that leave the theorem? Not proven as written. The gap may be fixable—perhaps one can argue that components with N_C=0 have small treewidth for other reasons, or redefine the weighting—but as it stands the main induction doesn't close. I would send this to a serious referee, because the idea is strong and the result is important, but I would not take it as a proof yet. I'd want to see a repair of Lemma 10 that excludes or handles the zero-weight case.\n\nMy reading-group vote is yes; there is a lot of usable technique here even if the paper needs revision.","headline":"A real improvement on clustered 3-colouring of planar graphs, with a genuine gap in the key induction of Lemma 10 that needs fixing.","tokens_in":14654,"tokens_out":3694,"would_cite":false,"duration_ms":40678,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C10","05C83"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every n-vertex planar graph is 3-colourable with clustering O(n^{4/9}), improving the previous O(n^{1/2}) bound.","keywords":["planar graphs","clustered colouring","3-colouring","monochromatic components","treewidth","graph separators","grid minors","face-weighting"],"falsifier":"Exhibit a connected plane graph $C$, a face-weighting, and a noose such that some component of $C$ minus the noose contains two or more faces that are not faces of $C$, while the total weight on that component is still above $2/3$ of the weight of $C$; that would directly violate the $|X_{C'}| \\le |X_C| + 1$ step in Lemma 10 and invalidate the stated proof of the $O(n^{4/9})$ bound.","tokens_in":13551,"feed_emoji":"🎨","tokens_out":8595,"duration_ms":93271,"temperature":0.7,"pith_summary":"This paper proves that every planar graph on n vertices can be coloured with three colours so that every connected monochromatic component has at most O($n^{{4/9}}$) vertices, improving the previous best guarantee of O($n^{{1/2}}$). Such a clustered colouring is the standard relaxation of proper colouring when only three colours are allowed, since the Four-Colour Theorem prohibits exact 3-colouring of many planar graphs. The result narrows the gap between the known lower bound $\\Omega(n^{1/3})$ and the best upper bound, and the proof introduces a separator construction of independent interest: a q-separator whose induced subgraph has treewidth only $O((n/q)^{1/2})$, not the naive $O(n^{1/2}/q^{1/4})$.","feed_headline":"Planar graphs 3-colourable with clustering O(n^{4/9})","feed_subtitle":"Improves the best known O(n^{1/2}) bound for splitting planar graphs into three colours with small monochromatic pieces.","key_machinery":"The engine is a face-weighting lemma (Lemma 10) that recursively cuts a connected subgraph along nooses, which are simple closed curves made of graph edges. The faces of a subgraph are weighted by the number of original vertices lying inside them; each cut is chosen by a weighted cycle-separator lemma so that the weight on every resulting component drops by at least a factor of $2/3$, while the number of faces that are new, meaning not inherited from the original graph, increases by at most one. This tradeoff, weight dropping geometrically while the hole count grows only linearly, yields the bound $|X_C| \\le \\log_{3/2} N$ that controls both the size and the treewidth of the separator. An embedding-preserving triangulation step and the linear grid-minor/treewidth bound for planar graphs, $\\mathrm{tw}(G) \\le 6\\,\\mathrm{gm}(G)+1$, are the planarity-specific ingredients that make the weighted separator possible.","core_discovery":"The central claim is that the clustered three-colouring problem for planar graphs admits a bound of $O(n^{4/9})$, not the $O(n^{1/2})$ obtained by repeatedly applying a single separator theorem. The proof chooses a first separator $S_0$ of size $O(n^{7/9})$ so that the red colour class has no large components, then shows that the graph induced on $S_0$ itself admits a separator $S_1$ of size $O(n^{4/9})$ after which the remaining graph has treewidth $O(n^{1/9})$; a final separator of size $O(n^{4/9})$ in that bounded-treewidth graph colours the remaining vertices blue, while $S_1$ together with the final separator, coloured yellow, has at most $O(n^{4/9})$ vertices. For sufficiently large $n$, the constant is explicit: the paper states a clustering bound of $16 n^{4/9}$.","pith_inferences":["The exponent $4/9$ is tied to the $2/3$ weight drop and the at-most-one-new-face induction; a stronger control on new faces would plausibly lower the exponent, so the gap to $n^{1/3}$ is a natural target for future work.","The same template may extend to other minor-closed classes that have a linear bound between treewidth and grid minors, such as graphs on surfaces of bounded genus; if the embedding-preserving triangulation step can be adapted, a similar $O(n^{4/9})$ clustering could follow there.","One could test Lemma 10 computationally on random plane triangulations: search for a noose whose removal creates two or more new faces in a component; if found, the proof's constant would need repair even if the theorem itself survives."],"forward_implications":["The clustered 3-colouring upper bound for planar graphs drops from $O(n^{1/2})$ to $O(n^{4/9})$, leaving a gap between that upper bound and the known $\\Omega(n^{1/3})$ lower bound.","The proof yields an explicit separator with $|S| = O(n/q^{1/2})$ and $\\mathrm{tw}(G[S]) = O((n/q)^{1/2})$ for every $q$, which is best possible up to constants by the grid example given in the paper.","Because all constants in the proof are explicit, the construction is in principle algorithmic: finding the separators and colouring the remaining bounded-treewidth graph gives the claimed clustering.","The face-weighting lemma applies to any plane graph and any non-negative face weights, so the separator result is not tied to the specific colouring application and can be used wherever weighted planar separation is needed."],"supporting_citations":[{"why":"Supplies the constant-factor planar separator theorem and the weighted-cycle-separator framework that Lemma 4 and Lemma 7 adapt.","marker":"[2]"},{"why":"Gives the previous $O(n^{1/2})$ upper bound and the q-separator colouring scheme that the new proof refines.","marker":"[24]"},{"why":"Provides the linear bound between grid minors and treewidth in planar graphs, used throughout to pass from separator size to treewidth.","marker":"[43]"},{"why":"Supplies the bounded-treewidth q-separator lemma used in the final step to colour the remaining graph.","marker":"[14]"},{"why":"Provides the embedding-preserving plane triangulation lemma needed to apply the weighted cycle-separator result to arbitrary plane graphs.","marker":"[4]"},{"why":"Establishes the baseline $O(\\sqrt{n})$ balanced separator theorem for planar graphs that motivates and anchors the separator hierarchy.","marker":"[25]"}],"fun_headline_variants":["Planar 3-color clustering bound drops to O(n^{4/9})","Clustered 3-coloring of planar graphs: new O(n^{4/9}) bound","Better clustered 3-coloring for planar graphs: O(n^{4/9})","O(n^{4/9}) clustering for 3-coloring planar graphs","Planar graphs 3-color with O(n^{4/9}) monochromatic components"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bound rests on the claim that cutting a component along a noose adds at most one new face that was not already a face of that component, so the number of such faces grows at most linearly through the recursive cuts; if one cut could create many new faces, the induction behind Lemma 10, and hence the constant 16, would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Planar 3-color clustering bound drops to O(n^{4/9})","Clustered 3-coloring of planar graphs: new O(n^{4/9}) bound","Better clustered 3-coloring for planar graphs: O(n^{4/9})","O(n^{4/9}) clustering for 3-coloring planar graphs","Planar graphs 3-color with O(n^{4/9}) monochromatic components"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000184,"raw_usage":{"total_tokens":1243,"prompt_tokens":793,"completion_tokens":450,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":409,"completion_tokens_details":{"reasoning_tokens":353}},"tokens_in":409,"tokens_out":450,"duration_ms":4173,"temperature":1.0,"reasoning_tokens":353,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:23:04.754328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a connected plane graph $C$, a face-weighting, and a noose such that some component of $C$ minus the noose contains two or more faces that are not faces of $C$, while the total weight on that component is still above $2/3$ of the weight of $C$; that would directly violate the $|X_{C'}| \\le |X_C| + 1$ step in Lemma 10 and invalidate the stated proof of the $O(n^{4/9})$ bound.","supporting_citations":[{"cited_title":"Planar separators.SIAM J","cited_arxiv_id":null,"evidence_quote":"Supplies the constant-factor planar separator theorem and the weighted-cycle-separator framework that Lemma 4 and Lemma 7 adapt."},{"cited_title":"Graph colouring with no large monochromatic components.Combin","cited_arxiv_id":null,"evidence_quote":"Gives the previous $O(n^{1/2})$ upper bound and the q-separator colouring scheme that the new proof refines."},{"cited_title":"Quickly excluding a planar graph","cited_arxiv_id":null,"evidence_quote":"Provides the linear bound between grid minors and treewidth in planar graphs, used throughout to pass from separator size to treewidth."},{"cited_title":"Drawing planar 3-trees with given face areas","cited_arxiv_id":null,"evidence_quote":"Provides the embedding-preserving plane triangulation lemma needed to apply the weighted cycle-separator result to arbitrary plane graphs."},{"cited_title":"Lipton and Robert E","cited_arxiv_id":null,"evidence_quote":"Establishes the baseline $O(\\sqrt{n})$ balanced separator theorem for planar graphs that motivates and anchors the separator hierarchy."}],"review_version":1}