Pith. sign in

REVIEW 1 major objections 6 minor 20 references

b-continuity and Partial Grundy Coloring of graphs with large girth

T0 review · 1 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Graphs with girth at least 8 admit b-colorings at every integer number of colors between the chromatic number and the b-chromatic number.

desk verdict 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. read the letter →

arxiv 1908.00674 v1 pith:3U6RMU6P submitted 2019-08-02 cs.DM math.CO

Allen Ibiapina , Ana Silva This is my paper · ORCID
classification cs.DMmath.CO MSC 05C1505C85
keywords b-coloringb-chromaticnumberb-continuityb-spectrumpartialGrundycoloringstairfactorgirth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

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.

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 (1)
  1. [Section 3, proof of Theorem 3] 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.
minor comments (6)
  1. [Section 2, definition of N_i(X)] 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.
  2. [Section 2, Lemma 2] 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)'.
  3. [Section 3, proof of Theorem 3] 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.
  4. [Section 3, proof of Theorem 3] The notation N_W(x) is used without definition; it should be defined as N(x) ∩ W.
  5. [Section 2 and Section 4] 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.
  6. [Lemma 3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central theorems are proved from stated girth hypotheses using external lemmas and original constructions, with no fitted inputs or self-citation chains.

full rationale

The paper's derivation chain is self-contained in the sense required by the circularity audit. Theorem 1 and Theorem 2 are obtained from Lemma 2, whose proof is given in full in Section 2, together with Lemma 1 quoted from Balakrishnan and Kavaskar. Lemma 1 is an external prior result, and the paper explicitly locates the girth-7 to girth-8 gap there: "the constraint about not having cycles of length 7 appears only in the above lemma, but not on our proof." This is honest dependence on published work, not a definitional reduction or a fitted input. Similarly, Theorem 3 proves that every feasible sequence of size s yields a partial Grundy coloring with s colors, relying on the upper bound and polynomial-time computability of the stair factor from Shi et al.; the construction is original and is not obtained by renaming or by assuming the equality it proves. Self-citations to Linhares-Sales and Silva appear only as prior context or as a stylistic comparison in Lemma 2's proof, and are not load-bearing; no uniqueness theorem from the authors is invoked to force the result. The skeptical note that the greedy argument in Theorem 3 uses m(y_i) < m(x) where a non-decreasing order only gives m(y_i) <= m(x) identifies a potential correctness gap, not circularity: a failed proof step does not make the claim equivalent to its inputs. No instance of self-definition, fitted-input-called-prediction, imported uniqueness, ansatz-smuggled-via-citation, or renaming of a known result was found.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

Pure graph theory paper with no fitted parameters and no new postulated objects. The only non-standard input is the cited Lemma 1, listed above.

assumptions (2)
  • domain assumption Lemma 1 of Balakrishnan and Kavaskar: a graph with girth at least 6, no cycles of length 7, and a k-iris with k >= chi(G) admits a b-coloring with k colors.
    Used to convert the (k-1)-iris produced by Lemma 2 into a b-coloring with k-1 colors; not proved in this paper.
  • standard math Standard definitions and bounds for b-colorings, partial Grundy colorings, and the stair factor from Irving and Manlove, Shi et al., and Campos and Silva.
    Background assumptions stated in the introduction and Section 3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of b-continuity and Partial Grundy Coloring of graphs with large girth." pith.science (2026). https://pith.science/paper/3U6RMU6P

@misc{pith2026190800674,
  author       = {Pith},
  title        = {Pith review of: b-continuity and Partial Grundy Coloring of graphs with large girth},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3U6RMU6P}},
  note         = {Machine review of arXiv:1908.00674}
}
abstract

A b-coloring of a graph is a proper coloring such that each color class has at least one vertex which is adjacent to each other color class. The b-spectrum of $G$ is the set $S_{b}(G)$ of integers $k$ such that $G$ has a b-coloring with $k$ colors and $b(G)=\max S_{b}(G)$ is the b-chromatic number of $G$. A graph is b-continous if $S_{b}(G)=[\chi(G),b(G)]\cap \mathbb{Z}$. An infinite number of graphs that are not b-continuous is known. It is also known that graphs with girth at least 10 are b-continuous. A partial Grundy coloring is a proper coloring $f:V(G)\rightarrow \{1,\ldots,k\}$ such that each color class $i$ contains some vertex $u$ that is adjacent to every color class $j$ such that $j<i$. The partial Grundy number of $G$ is the maximum value $\partial\Gamma(G)$ for which $G$ has a partial Grundy coloring. In this work, we prove that graphs with girth at least 8 are b-continuous, and that the b-spectrum of a graph $G$ with girth at least 7 contains the integers between $2\chi(G)$ and $b(G)$. We also prove that $\partial\Gamma(G)$ equals a known upper bound when $G$ is a graph with girth at least 7. These results generalize previous ones by Linhares-Sales and Silva (2017), and by Shi et al.(2005).

Figures

Figures reproduced from arXiv: 1908.00674 by the authors.

Figure 1
Figure 1. In the figure, we present a 4-iris. the lemma above. We mention that the constraint about not having cycles of length 7 appears only in the above lemma, but not on our proof. We now introduce the further needed definitions. Let G be a simple graph and ψ be a b-coloring of G with k > χ(G) + 1 colors. We say that u realizes color i if ψ(u) = i and u is a b-vertex. We also say that color i is realized by u. For x ∈ V (… view at source ↗
Figure 2
Figure 2. Structure around u when color k does not satisfy Claim 2.(ii). Now, to prove Theorem 2, we apply Lemma 2 and the next lemma. A star is a tree that has at most one vertex with degree bigger than 1, and the diameter of a graph G is the maximum number of edges in a shortest path of G [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. 1 u u2 2 u3 3 . . . uk k N2 N3 . . . Nk 1 2 . . . k 1 2 . . . k 1 2 . . . k T {w ∈ V (G) \ T | ∃x ∈ N(w) s.t. ψ(x) ∈ {1, . . . , χ(G)}} B [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Subset of vertices in the vicinity of x. Black vertices are in W. Square vertices are in {u1, . . . , uℓ}. Observe that no two of them are equal since G has girth at least 7. in [15], where they prove that graphs with girth at least 10 are b-continuous. There, the auth…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Balakrishnan and T

    R. Balakrishnan and T. Kavaskar. b-coloring of kneser gra phs. Discrete Appl. Math., 160:9– 14, 2012. b-continuity and Partial Grundy Coloring of graphs with lar ge girth 11

    work page 2012

  2. [2]

    Balakrishnan and T

    R. Balakrishnan and T. Kavaskar. Interpolation theorem f or partial grundy coloring. Discrete Math., 313(8):949–950, 2013

    work page 2013

  3. [3]

    Barth, J

    D. Barth, J. Cohen, and T. Faik. On the b-continuity proper ty of graphs. Discrete Appl. Math., 155:1761–1768, 2007

    work page 2007

  4. [4]

    Bondy and U.S.R

    A. Bondy and U.S.R. Murty. Graph Theory. Spring-V erlag Press, 2008

    work page 2008

  5. [5]

    Cabello and M

    S. Cabello and M. Jakovac. On the b-chromatic number of reg ular graphs. Discrete Appl. Math., 159:1303–1310, 2011

    work page 2011

  6. [6]

    Christen and S.M

    C.A. Christen and S.M. Selkow. Some perfect coloring prop erties of graphs. Journal of Combinatorial Theory B , 27:49–59, 1979

    work page 1979

  7. [7]

    D.P . Dailey. Uniqueness of colorability and colorabilit y of planar 4-regular graphs are np- complete. Discrete Math., 30(3):289–293, 1980

    work page 1980

  8. [8]

    Erd ˝os, S.T

    P . Erd ˝os, S.T. Hedetniemi, R. Laskar, and G.C.E. Prins. On the equa lity of the partial grundy and upper ochromatic numbers of graphs. Discrete Math., 272(1):53–64, 2003

    work page 2003

Show all 20 references
  1. [9]

    Havet, C

    F. Havet, C. Linhares-Sales, and L. Sampaio. b-coloring o f tight graphs. Discrete Appl. Math., 160(18):2709–2715, 2012

    2012

  2. [10]

    I. Holyer. The np-completeness of edge-coloring. SIAM J. on Computing , 10(4):718–720, 1981

    1981

  3. [11]

    Irving and D.F

    R.W. Irving and D.F. Manlove. The b-chromatic number of a graph. Discrete Appl. Math. , 91:127–141, 1999

    1999

  4. [12]

    R. Karp. Reducibility among combinatorial problems. Complexity of Computations, Ad- vances in Computer Research, 85–103, 1972

    1972

  5. [13]

    Kratochvíl, Zs

    J. Kratochvíl, Zs. Tuza, and M. V oigt. On the b-chromatic number of graphs. In WG 2002 - Int. W orkshop on Graph-Theoretic Concepts in Comp. Sc., 2002

    2002

  6. [14]

    Lin and G.J

    W.-H. Lin and G.J. Chang. b-coloring of tight bipartite g raphs and the erdos–faber–lovász conjecture. Discrete Appl. Math., 161(7-8):1060–1066, 2013

    2013

  7. [15]

    Linhares-Sales and A

    C. Linhares-Sales and A. Silva. The b-continuity of grap hs with large girth. Graphs and Combinatorics, 33(5):1139–1146, 2017

    2017

  8. [16]

    Lozin and M

    V .V . Lozin and M. Kaminski. Coloring edges and vertices o f graphs without short or long cycles. Contributions do Discrete Mathematics, 2(1), 2007

    2007

  9. [17]

    Maffray M

    F. Maffray M. Blidia and Z. Zemir. On b-colorings in regul ar graphs. Discrete Appl. Math., 157:1787–1793, 2009

    2009

  10. [18]

    El Sahili and H

    A. El Sahili and H. Kouider. About b-colouring of regular graphs. Utilitas Math., 80:211– 215, 2009

    2009

  11. [19]

    Z. Shi, W. Goddard, S.T. Hedetniemi, K. Kennedy, R. Laska r, and A. McRae. An algorithm for partial Grundy number on trees. Discrete Math., 304:108–116, 2005

    2005

  12. [20]

    C. Lima V . Campos and A. Silva. Graphs with girth at least 7 have high b-chromatic number. European Journal of Combinatorics, 48:154–164, 2015

    2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.