{"id":"01d7065f-a927-4e97-b87d-7531f024eeef","arxiv_id":"1908.00674","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphs with girth at least 8 are b-continuous, and girth at least 7 gives partial Grundy number equal to the stair factor.","lead":"This paper proves that graphs whose shortest cycle has length at least 8 are b-continuous, improving a known bound of 10, and that graphs with girth at least 7 have every color count from twice the chromatic number up to the b-chromatic number. It also shows that for girth at least 7 the partial Grundy number equals a known computable upper bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's greedy-coloring proof asserts m(y_i) < m(x) from a non-decreasing order; ties are not excluded, so the u_i need not lie in W_<ell and the pigeonhole/cycle contradiction does not follow as written.","rationale":"The reader's stated weakest assumption is the inherited iris lemma, Lemma 1. That is a legitimate dependency, and the authors themselves flag it in Section 4 by observing that Theorem 1 is restricted to girth at least 8 'just because of Lemma 1'. However, reliance on a published lemma is not by itself a flaw of this paper, and I do not find a concrete error there. The internal step in Section 3 is more immediately load-bearing: the proof of Theorem 3 rests on a pigeonhole contradiction that requires strict inequality m(y_i) < m(x). The text only specifies a non-decreasing order, so equal values are allowed and the map into W_<ell can fail. This is exactly the compressed point the reader mentions in the rationale, though not in the weakest_assumption field. The rest of the paper contains substantial coherent work: the counting argument in Lemma 2 around equations (1)-(4) is intricate, and Lemma 3's star-coloring extension is plausible. No machine-checked proof or reproducible code is supplied to compensate. I therefore recommend keeping the conditional verdict: the results may hold, but the proof of Theorem 3 needs a repaired tie-breaking argument, and Theorem 1 remains hostage to the correctness of Lemma 1.","tokens_in":9661,"tokens_out":30406,"duration_ms":313711,"concrete_test":"Implement the described greedy algorithm and enumerate all graphs with girth at least 7 on up to 10 vertices, together with all feasible sequences W and all allowed choices of N_i; check whether any execution reaches an iteration of x with ell = m(x) where every color 1,...,ell-1 is in psi(F) and at least one witness y_i has m(y_i) = ell. If such an instance exists, the proof as written is incomplete; if none exists, state and prove the tie-breaking rule that makes m(y_i) < m(x) for every earlier-colored y_i in F, and re-run the pigeonhole step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3, the proof of Theorem 3 defines m(x) = min{i : w_i in N(x)} and colors N in non-decreasing order of m(x). At the step for x, if no color in {1,...,ell-1} outside psi(F) exists, the proof selects y_i in F with psi(y_i)=i. For y_i in N, it sets u_i = w_{m(y_i)} and claims: by the chosen order of coloring, m(y_i) < m(x). A non-decreasing order only gives m(y_i) <= m(x). If m(y_i) = m(x) = ell, then u_i = w_ell, which is not in W_<ell = {w_2,...,w_{ell-1}}. Since the argument needs all ell-1 vertices u_i to lie in a set of size ell-2 in order to force a repetition and then a short cycle, a single tie breaks the pigeonhole step. The earlier note that a colored x satisfies psi(x) < m(x) is also not a consequence of non-redundancy; it is only an invariant of the proposed greedy choices, and it does not rule out equal m among already-colored vertices. This is a gap in the proof that partial-Grundy(G) = s(G) for girth at least 7 and that an optimal partial Grundy coloring can be obtained in polynomial time. The theorem may still be true, but this step needs a tie-breaking rule or a different argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies b-coloring and partial Grundy coloring in graphs with large girth. It claims three main theorems: (1) every graph with girth at least 8 is b-continuous; (2) every graph with girth at least 7 has [2χ(G), b(G)] ⊆ S_b(G); and (3) for graphs with girth at least 7, the partial Grundy number equals the stair factor s(G), and an optimal partial Grundy coloring can be found in polynomial time. The proofs introduce a reduction lemma (Lemma 2) showing that a b-coloring with k colors either yields a (k−1)-coloring or contains a (k−1)-iris, and a construction lemma (Lemma 3) turning a k-iris with k ≥ 2χ into a b-coloring. Theorem 3 is proved via feasible sequences and a greedy non-redundant coloring of the neighbor set N.","tokens_in":9928,"tokens_out":38650,"duration_ms":341719,"significance":"If the results hold, they improve the known girth threshold for b-continuity from 10 to 8 and for the partial Grundy equality from 9 to 7, and they narrow the range for the minimum girth parameters posed in the literature. The paper is well organized and the counting arguments in Lemmas 2 and 3 are mostly clear. The main weakness is a gap in the proof of Theorem 3, which is load-bearing for the claimed equality and polynomial-time algorithm. The paper also relies on Lemma 1 from a previous paper without proof, as the authors transparently acknowledge.","major_comments":[{"comment":"The step 'by the chosen order of coloring, we get that m(y_i) < m(x)' is unjustified. The vertices of N are colored in non-decreasing order of m, so for an already colored vertex y_i the non-decreasing order only gives m(y_i) ≤ m(x). The strict inequality is needed to conclude that u_i = w_{m(y_i)} lies in W_<ℓ = {w_2,...,w_{ℓ−1}}. Equality m(y_i) = m(x) = ℓ is not excluded by the hypotheses: take y_i ∈ N_ℓ with y_i adjacent to w_ℓ, and x adjacent to w_ℓ but not to y_i; this configuration is compatible with girth at least 7 and with y_i being colored before x under an arbitrary tie-breaking. In that case u_i = w_ℓ ∉ W_<ℓ, so the set {u_1,...,u_{ℓ−1}} is contained in a set of size ℓ−1 (namely W_<ℓ ∪ {w_ℓ}) rather than ℓ−2, and the pigeonhole argument no longer forces a repeated vertex. Consequently the claimed contradiction is not established. A tie-breaking rule or an additional argument is needed. Since this is the central argument for ∂Γ(G) = s(G) and for the polynomial-time algorithm, the proof of Theorem 3 is incomplete as written.","section":"Section 3, proof of Theorem 3"}],"minor_comments":[{"comment":"The displayed definition of N_i(X) contains a typo ('N_i(X) = ⋃_{x∈X} N_i(X) \\ X'); it should read N_i(X) = (⋃_{x∈X} N_i(x)) \\ X.","section":"Section 2, definition of N_i(X)"},{"comment":"In the statement of Claim (iii), 'N_d(B_d) ⊆ N_j(u)' should presumably be 'N_j(B_d) ⊆ N_j(u)' to match the definition of dependence (color d depends on N_j(u) if N_j(B_d) ⊆ N_j(u)). Similarly, in the final paragraph, 'N_2(B_k) ⊆ N_2(u)' should likely be 'N_k(B_2) ⊆ N_k(u)'.","section":"Section 2, Lemma 2"},{"comment":"The sentence 'Note that if ψ is a non-redundant partial coloring and x is colored in ψ, then ψ(x) < m(x)' is false for an arbitrary non-redundant coloring; it is an invariant of the particular greedy construction (a vertex is always assigned a color smaller than its current m). Please rephrase to avoid implying it follows from non-redundancy alone.","section":"Section 3, proof of Theorem 3"},{"comment":"The notation N_W(x) is used without definition; it should be defined as N(x) ∩ W.","section":"Section 3, proof of Theorem 3"},{"comment":"Theorem 1 depends entirely on Lemma 1 from [1], which is not proved in this manuscript. The authors explicitly note that the 7-cycle condition appears only in that lemma and that the girth-8 restriction is due to it. Since the continuity result rests on this external result, the paper would be easier to verify if the lemma statement were accompanied by a proof sketch or a precise pointer to the original statement.","section":"Section 2 and Section 4"},{"comment":"The set B should be defined explicitly as a subset of V(G)\\T, because the subsequent argument colors G[B] and G−T−B as disjoint sets.","section":"Lemma 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically interesting and likely correct after fixing the gap in Theorem 3. I recommend that the editor verify the exact statement of Lemma 1 in reference [1], as the b-continuity theorem depends on it entirely and the authors do not reproduce its proof. The proof of Theorem 3 needs a substantive revision; the remaining issues are presentation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here’s my read. The paper genuinely improves known thresholds: b-continuity from girth 10 down to 8, an intermediate interval [2χ, b] for girth 7, and partial Grundy equality with the stair factor at girth 7. Lemma 2 is a real refinement of the Linhares-Sales–Silva approach, concentrating on a single color class, and the proofs of Theorems 1 and 2 look coherent to me. The paper is also honest about relying on the external iris lemma from Balakrishnan and Kavaskar; that is a normal, acceptable reliance, not a flaw.\n\nThe problem is Theorem 3. The proof colors N in non-decreasing order of m(x), then at the key step claims that for an already colored y_i we have m(y_i) < m(x). Non-decreasing only gives ≤. If equality holds, then u_i = w_ell, which is not in W_<ell, and the pigeonhole argument collapses. The earlier note that a colored x satisfies ψ(x) < m(x) does not rule out equal m values among already-colored vertices. This is a genuine gap in the proof as written. The theorem may still be true, but the current argument does not establish it.\n\nApart from that, the paper is solid. The b-continuity results are the main event and are not undermined by this gap. The citation pattern looks appropriate: they build on the right prior work and are clear about what is new. No data issues, since it is a pure theory paper.\n\nWho is this for? Specialists in graph coloring, especially those interested in b-colorings and Grundy colorings. I would send it to a graph theory journal, but require a revision on Theorem 3. If the authors supply a valid ordering argument or a different proof, the paper becomes a solid contribution.\n\nRecommendation: yes, it deserves serious peer review, with the expectation that the partial Grundy gap be fixed.","headline":"Makes real progress on girth thresholds for b-continuity, but the proof of Theorem 3 has a genuine gap that needs repair before the partial Grundy result is established.","tokens_in":10480,"tokens_out":5463,"would_cite":true,"duration_ms":52325,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C15","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Graphs with girth at least 8 admit b-colorings at every integer number of colors between the chromatic number and the b-chromatic number.","keywords":["b-coloring","b-chromatic number","b-continuity","b-spectrum","partial Grundy coloring","partial Grundy number","stair factor","girth"],"falsifier":"A computational enumeration of girth-8 graphs checking every integer between the chromatic number and the b-chromatic number would find a counterexample if one exists; in particular, a single girth-8 graph with chromatic number 3, b-chromatic number 5, and no b-coloring with 4 colors would refute Theorem 1, and a girth-7 graph with the same property would show the threshold cannot be lowered to 7.","tokens_in":9445,"feed_emoji":"🎨","tokens_out":6422,"duration_ms":60690,"temperature":0.7,"pith_summary":"This paper establishes that large-girth graphs have well-behaved b-colorings. The main result is Theorem 1: if a graph has girth at least 8, then for every integer k between its chromatic number and its b-chromatic number, the graph admits a b-coloring using exactly k colors. The paper also proves that for girth at least 7, the b-spectrum contains all integers from 2 times the chromatic number up to the b-chromatic number, and that the partial Grundy number equals the stair factor, with an optimal partial Grundy coloring computable in polynomial time. These results narrow the unknown threshold for universal b-continuity to between 5 and 8, improving earlier girth-10 results.","feed_headline":"No missing b-color counts in girth-8 graphs","feed_subtitle":"A graph with no cycles shorter than 8 admits a b-coloring with every number of colors from minimum to maximum.","key_machinery":"The proof is carried by two structural objects. A k-iris is a vertex u with at least k-1 neighbors, each of degree at least k-1. The paper's Lemma 2 says that for girth at least 7, any b-coloring with k >= chromatic number plus one that cannot be reduced to k-1 colors forces a (k-1)-iris. The complementary step, that an iris yields a b-coloring, is a previously published lemma restricted to graphs without 7-cycles; that borrowed lemma is why the continuity theorem requires girth 8 rather than 7 and is not reproved in the paper. For the partial Grundy result, the machinery is the feasible sequence (w1,...,ws) with each wi having at least i-1 neighbors in the remaining graph, together with a non-redundant coloring of the selected neighborhoods; the girth-7 condition ensures that a greedy coloring of these neighborhoods can always be completed, since otherwise two shortcuts would create a short cycle.","core_discovery":"The central claim is that forbidding cycles shorter than length 8 makes the b-spectrum gap-free: for every graph G with girth at least 8, the set of integer k for which G has a b-coloring is exactly the full interval from the chromatic number to the b-chromatic number. The proof works by taking any b-coloring with k >= chromatic number plus one and showing that either one color can be removed to get a b-coloring with k-1 colors, or the graph contains a k-iris, a vertex with many high-degree neighbors. A previously published lemma then converts that iris into the missing b-coloring. For girth at least 7, the same step yields the weaker statement that every k between twice the chromatic number and the b-chromatic number appears in the spectrum. Separately, the paper shows that a feasible sequence of length s, which gives the stair-factor upper bound, can always be turned into a partial Grundy coloring with s colors when the girth is at least 7, so the partial Grundy number equals the stair factor.","pith_inferences":["Because the paper identifies the borrowed iris lemma as the only place the 7-cycle condition matters, a natural testable extension is to prove or disprove that lemma's analogue for girth 7; a positive answer would lower the universal threshold to 7.","A computational search over girth-7 graphs for a k-iris with k at least the chromatic number plus one that fails to yield a b-coloring would answer the paper's Question 3 and show that girth 8 is best possible.","The same counting argument in Lemma 2 may adapt to bipartite graphs of girth 6, and the paper notes a connection to a standing conjecture on tight bipartite graphs; a concrete next step is to search girth-6 bipartite graphs for such a failing iris, which would settle the tightness of that conjecture.","The polynomial-time partial Grundy result for girth 7 suggests that the known interpolation property for partial Grundy colorings might combine with the stair factor to produce a certificate for the partial Grundy number, though the paper does not pursue this."],"forward_implications":["For every graph of girth at least 8, the b-spectrum is the full integer interval from the chromatic number to the b-chromatic number, so once those endpoints are known, every intermediate color count is known to be realizable.","For girth at least 7, at most the first few values above the chromatic number can be missing from the b-spectrum; every count from twice the chromatic number up to the b-chromatic number is guaranteed present.","For girth at least 7, the partial Grundy number is exactly the stair factor, so the known polynomial-time computation of a maximum feasible sequence also yields an optimal partial Grundy coloring.","The known non-b-continuous graphs built from complete bipartite graphs minus a matching show that the universal girth threshold for b-continuity is at least 5; the paper leaves the exact threshold in the range 5 to 8."],"supporting_citations":[{"why":"Supplies the previously published lemma, used as a black box, that a k-iris in a graph without 7-cycles forces a b-coloring with k colors; Theorem 1 stands on this lemma.","marker":"[1]"},{"why":"Gives the earlier girth-10 b-continuity result and the proof template that Lemma 2 adapts, and poses the questions about the exact threshold.","marker":"[15]"},{"why":"Defines feasible sequences and the stair factor s(G), proves s(G) is an upper bound for the partial Grundy number, and establishes equality for girth at least 9; Theorem 3 extends this to girth 7.","marker":"[19]"},{"why":"Shows that graphs with girth at least 7 have high b-chromatic number, providing the context that Theorem 2 refines into a spectrum statement.","marker":"[20]"},{"why":"Provides the complete bipartite graphs minus a perfect matching that are not b-continuous, giving the lower bound of 5 for the universal girth threshold.","marker":"[13]"}],"fun_headline_variants":["Girth-8 graphs have no b-color gaps","Forbidding short cycles fills coloring spectrum","Girth 7 graphs meet partial Grundy bound","b-continuity proven for girth at least 8","All b-colorings realized in girth-8 graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The girth-8 continuity theorem rests on a previously published lemma, not proved in this paper, that a graph with no short cycles and a special high-degree neighborhood must admit a b-coloring; if that lemma is wrong or needs stronger hypotheses, the main theorem does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Girth-8 graphs have no b-color gaps","Forbidding short cycles fills coloring spectrum","Girth 7 graphs meet partial Grundy bound","b-continuity proven for girth at least 8","All b-colorings realized in girth-8 graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000257,"raw_usage":{"total_tokens":1646,"prompt_tokens":1080,"completion_tokens":566,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":489}},"tokens_in":696,"tokens_out":566,"duration_ms":5825,"temperature":1.0,"reasoning_tokens":489,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:40:26.128212+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A computational enumeration of girth-8 graphs checking every integer between the chromatic number and the b-chromatic number would find a counterexample if one exists; in particular, a single girth-8 graph with chromatic number 3, b-chromatic number 5, and no b-coloring with 4 colors would refute Theorem 1, and a girth-7 graph with the same property would show the threshold cannot be lowered to 7.","supporting_citations":[{"cited_title":"Balakrishnan and T","cited_arxiv_id":null,"evidence_quote":"Supplies the previously published lemma, used as a black box, that a k-iris in a graph without 7-cycles forces a b-coloring with k colors; Theorem 1 stands on this lemma."},{"cited_title":"Linhares-Sales and A","cited_arxiv_id":null,"evidence_quote":"Gives the earlier girth-10 b-continuity result and the proof template that Lemma 2 adapts, and poses the questions about the exact threshold."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines feasible sequences and the stair factor s(G), proves s(G) is an upper bound for the partial Grundy number, and establishes equality for girth at least 9; Theorem 3 extends this to girth 7."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that graphs with girth at least 7 have high b-chromatic number, providing the context that Theorem 2 refines into a spectrum statement."},{"cited_title":"Kratochvíl, Zs","cited_arxiv_id":null,"evidence_quote":"Provides the complete bipartite graphs minus a perfect matching that are not b-continuous, giving the lower bound of 5 for the universal girth threshold."}],"review_version":1}