Sharp quadratic $\chi$-binding functions for powers of bipartite graphs

Arpan Sadhukhan; Suraj Kumar Sahoo

Sharp quadratic $\chi$-binding functions for powers of bipartite graphs

T0 review · 0 major / 6 minor · reviewed 2026-08-28 · deepseek-v4-flash

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

Pith's one-line read For every fixed power $r \geq 2$, the chromatic number of an $r$-th power of a bipartite graph can be quadratic in its clique number, making the simple ball-counting upper bound asymptotically exact.

desk verdict Clean asymptotic resolution of an open problem on chi-binding functions for powers of bipartite graphs; the probabilistic construction checks out. read the letter →

arxiv 2608.27396 v1 pith:HBLSOXXA submitted 2026-08-27 math.CO

Arpan Sadhukhan , Suraj Kumar Sahoo This is my paper · ORCID

classification math.CO MSC 05C1205C1505C5005C80

keywords graphpowerschromaticnumbercliquebipartitegraphschi-boundednessprojectiveplaneprobabilisticmethodcoloring

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

The paper proves that for every fixed power $r \geq 2$, the largest chromatic number of an $r$-th power of a bipartite graph with clique number $t$ grows as $\Theta_r(t^2)$. This means the straightforward quadratic upper bound obtained by counting balls of radius $r$ cannot be improved in general. The proof constructs random graphs from the incidence structure of a projective plane, splitting each line into two signed copies, so that the square has many vertices but no large cliques. The same construction, after subdividing edges, handles all higher powers. This settles the open question of whether squares of bipartite graphs admit a subquadratic $\chi$-binding function: they do not.

What carries the argument

The central object is the random signed-split projective-plane graph $\Gamma_q$: take the point-line incidence graph of $\mathrm{PG}(2,q)$, replace each line vertex by two signed copies, and assign each incidence $(p,\ell)$ independently to one of the two copies with probability $\rho = q^{-1/3}$. This construction keeps the square's clique number linear, at most $4q$, while the point side retains about $q^2$ vertices with independence number at most $13$, forcing $\chi(\Gamma_q^2) \geq (q^2+q+1)/13$. For $r \geq 4$, the $L$-subdivision lemma with $L = \lfloor r/2 \rfloor$ multiplies distances by $L$, making the $r$-th power on original vertices equal to the square, while adding at most $4(L-1)\Delta$ vertices to any clique.

What would settle it

Run the random construction of Section 4 for a sequence of increasing prime powers $q$ and test the three estimates of Lemma 4.2: the maximal size of an independent set in $\Gamma_q^2[A_q]$, and the clique numbers of $\Gamma_q^2[A_q]$ and $\Gamma_q^2[B_q]$. If for infinitely many $q$ the point-side independence number exceeds 13 or either clique number reaches $4q$ with probability bounded away from zero, the existence theorem for squares fails. A direct check of the independence of the 91 pair-events on a single 14-point arc would isolate the crux.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 1.1: for every fixed integer $r \geq 2$, $f_r(t) = \Theta_r(t^2)$, where $f_r(t) = \sup\{\chi(G^r) : G \text{ is bipartite and } \omega(G^r) \leq t\}$. The quadratic upper bound $\chi(G^r) \leq 2\omega(G^r)^2$ is therefore asymptotically sharp. For squares, the witness is a random signed-split projective-plane graph $\Gamma_q$ with about $q^2$ point-vertices, square chromatic number at least $(q^2+q+1)/13$, and square clique number at most $4q$. For higher powers, an $L$-subdivision of this graph preserves the square's chromatic lower bound while adding only a linear number of vertices to any clique, yielding the quadratic lower bound for every $r \geq 3$.

Load-bearing premise

The load-bearing premise is that the random signed-split graph simultaneously satisfies the three estimates of Lemma 4.2—point-side independence number at most 13 and both side clique numbers below $4q$—with probability tending to 1; if the assumed independence of the pair-events or the union-bound exponents fails, the quadratic lower bound collapses.

Editorial extensions

If this is right

The quadratic upper bound $\chi(G^r) \leq 2\omega(G^r)^2$ is tight up to constants for every fixed $r \geq 2$, so no general subquadratic $\chi$-binding function exists for powers of bipartite graphs.
The class of squares of bipartite graphs is not subquadratically $\chi$-bounded, answering the earlier open question in the negative.
The girth restriction in the subquadratic result for girth greater than $6$ is essential: the constructed graphs have girth exactly $6$.
For higher powers, the lower-bound constant is on the order of $1/r^2$, matching the order of the upper-bound constant, so the quadratic behavior persists for all $r \geq 2$.

Reading between the lines

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

The random signed-splitting idea likely transfers to any $C_4$-free bipartite incidence graph with many vertices and bounded degree, so quadratic lower bounds for squares may extend to other incidence geometries, not just projective planes.
The construction has girth exactly $6$, indicating that the girth-$6$ case is the genuine bottleneck for $\chi$-binding of squares of bipartite graphs.
The proof establishes existence with high probability; a derandomized construction would make the lower-bound graphs explicit and potentially useful for algorithmic distance-coloring questions.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: The central discovery is Theorem 1.1: for every fixed integer $r \geq 2$, $f_r(t) = \Theta_r(t^2)$, where $f_r(t) = \sup\{\chi(G^r) : G \text{ is bipartite and } \omega(G^r) \leq t\}$. The quadratic upper bound $\chi(G^r) \leq 2\omega(G^r)^2$ is therefore asymptotically sharp. For squares, the witness is a random signed-split projective-plane graph $\Gamma_q$ with about $q^2$ point-vertices, squar

/-- @claim 1 The central discovery is Theorem 1.1: for every fixed integer $r \geq 2$, $f_r(t) = \Theta_r(t^2)$, where $f_r(t) = \sup\{\chi(G^r) : G \text{ is bipartite and } \omega(G^r) \leq t\}$. The quadratic upper bound $\chi(G^r) \leq 2\omega(G^r)^2$ is therefore asymptotically sharp. For squares, the witness is a random signed-split projective-plane graph $\Gamma_q$ with about $q^2$ point-vertices, squar -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Dear Colleague,

Short version: this is a clean, correct resolution of an open problem, and the main construction is genuinely new. It deserves a serious referee and will be cited.

What's new: for every fixed r>=2, f_r(t) = Theta_r(t^2), where f_r(t) is the supremum of chi(G^r) over bipartite G with omega(G^r) <= t. The open case was r=2; the paper settles it and all higher powers at once. The upper bound is elementary ball-counting (Lemmas 3.1-3.2). The lower bound is the real work: take the incidence graph of PG(2,q), replace each line-vertex by two signed copies, and for each point-line incidence flip a Bernoulli variable with rho=q^{-1/3} to decide which copy the point attaches to. The point side of the square has no 14-vertex independent set with high probability (arcs have distinct pair-lines, giving independence among the 91 pair-events), so chi >= (q^2+q+1)/13, while both sides and mixed cliques in the square have size O(q). The union-bound exponents work out: e^{-2q^{5/3}} beats the e^{O(q log q)} counting. For r>=3, an L-subdivision argument lifts the square lower bound while controlling new cliques by a C4-free case analysis that gives a linear-in-Delta bound on internal vertices.

I checked the delicate parts. Lemma 4.2(i) is valid because an arc has no three collinear points, so distinct pairs determine distinct lines and hence distinct incidence variables. Lemma 4.2(ii)-(iii) have the right forced-incidence count M >= s(q+1)-N, and the exponents dominate. Lemma 5.2's |F| <= 4Delta argument is intricate but the 4-cycle exclusions are correct. Theorem 1.1 follows with Bertrand's postulate; the constant 1/832 is not optimized, which is irrelevant.

Soft spots are minor: the construction is probabilistic and non-explicit; the constants are arbitrary; the title's 'sharp' means asymptotically sharp, not exact constant, which is clear from context. Remark 4 is a nice consistency check. The AI-assistance declaration is honest and the proofs are printed in full.

Who should read it: anyone working on chi-boundedness, graph powers, or the probabilistic method in extremal graph theory. It fits a journal like JGT or Combinatorics Probability and Computing. I would send it to a referee without hesitation. My own verdict matches the reader's: accept.

Recommendation: engage with it; it deserves a full review. No red flags.

Referee Report

0 major / 6 minor

Summary. This paper proves Theorem 1.1: for every fixed integer r≥2, the function f_r(t)=sup{χ(G^r): G bipartite, ω(G^r)≤t} satisfies f_r(t)=Θ_r(t^2). The upper bound is elementary: Lemmas 3.1 and 3.2 show χ(G^r)≤2ω(G^r)^2 for every bipartite G. The lower bound is obtained from a random construction based on the incidence graph of PG(2,q). Each line-vertex is split into two signed copies, with a random Bernoulli sign for every point-line incidence. Lemma 4.2 proves that with high probability the point side has independence number at most 13 and both the point and line sides have clique number less than 4q. This yields a bipartite C4-free graph Γ_q with χ(Γ_q^2)≥(q^2+q+1)/13 and ω(Γ_q^2)≤4q (Theorem 4.3). For powers r≥3, the square examples are uniformly subdivided: Lemma 5.2 shows that for G=S_L(H), G^r[V(H)]=H^2 and ω(G^r)≤ω(H^2)+4(L−1)Δ(H), which gives the quadratic lower bound for every fixed r (Theorem 5.3). Bertrand's postulate converts the prime-power family into a lower bound for all sufficiently large t, completing the proof.

Significance. The result settles the open problem of Chakraborty, Chandran, Jacob, and Pillai on squares of bipartite graphs, and strengthens it to all powers r≥2. The lower-bound construction is the main contribution: it shows that the straightforward ball-counting upper bound is asymptotically tight, despite the fact that square cliques in the incidence graph of a projective plane are as large as the whole vertex set. The probabilistic estimates are carefully executed; in particular, the independence of the 91 pair-events in Lemma 4.2(i) is valid because distinct pairs of an arc determine distinct projective lines. The subdivision lemma for higher powers is also sound. The paper is clearly written and contains complete proofs of the projective-plane facts it uses. If the result holds (and the proof appears correct), it is a significant contribution to the chi-boundedness literature for graph powers.

minor comments (6)

[Section 5] The L-subdivision is numbered Definition 1, duplicating the graph-power definition in Section 2; please renumber it as Definition 5.1 (or similar).
[Lemma 5.2] The assertion that G=S_L(H) is bipartite is correct, but the one-sentence justification is too terse for the case of even L, where the bipartition of H does not extend directly to G; please add a short explanation (for example, for even L, color every original vertex with one color and alternate the internal vertices of each subdivided path).
[Lemma 4.2(iii)] The sentence 'the forced incidence variables are distinct and independent' would benefit from a brief justification that an incidence is a point-line pair, so two forced incidences are distinct even when they involve the same point or the same line.
[Proof of Theorem 1.1] Bertrand's postulate is invoked for a real x; please state explicitly that the version used is 'for every sufficiently large real x there is a prime q with x≤q≤2x', or apply the integer version to x=t/(2C_r).
[Lemma 4.2(ii)-(iii)] The expression '-sq^{2/3}/2' is a little opaque; since s=4q it equals -2q^{5/3}, and writing the latter form directly would improve readability.
[Throughout] There are a few grammatical slips (e.g., 'Hence by using different sets of colors for A and B gives a proper coloring' in Lemma 3.2) that should be corrected in copyediting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound rests on an independent probabilistic construction and the upper bound on elementary ball counting.

full rationale

The paper's central claim, Theorem 1.1, is assembled from two independent estimates. The quadratic upper bound (Lemmas 3.1 and 3.2) is a direct ball-counting argument using that balls of radius s are cliques in the r-th power. The quadratic lower bound is obtained by a probabilistic construction: Lemma 4.2 separately bounds the independence number of the point-side square (via counting 14-point arcs and pairwise independent incidence events) and the clique number on both sides (via union bounds over signed sets). These quantities are not derived from each other, and the parameter rho = q^{-1/3} is chosen only to make the union-bound exponents negative, not fitted to any target chromatic-to-clique ratio. The subdivision argument in Lemma 5.2 is a deterministic reduction showing that the r-th power of the subdivided graph preserves the square chromatic number of the original vertices while increasing clique number by at most O(L Delta); it does not assume the desired quadratic relation. The paper cites prior work for context and for the open problem, but no load-bearing step is justified only by a self-citation, and no fitted input is renamed as a prediction. The derivation is self-contained against the stated probabilistic estimates and standard projective-plane facts.

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

The lower bound rests on one hand-chosen probability parameter (rho) and convenience thresholds (14, 13, 4q); none are fitted to data, and the asymptotic claim is insensitive to their exact values. All other inputs are standard mathematics (projective-plane facts, Bertrand's postulate, probabilistic method tools). The paper introduces no postulated entities: the signed line-vertices are explicit objects of the construction, and the only external theorem used for orientation is the cited girth > 6 subquadratic result of [3], which appears in Remark 4 as a consistency check and is not load-bearing.

free parameters (2)

rho (splitting probability) = q^{-1/3}
Bernoulli probability for the random labels xi(p,ell) in the Section 4 Construction. Chosen by hand so the Lemma 4.2 union bounds hold: rho must satisfy roughly (log q)/q < rho < q^{-28/91}, and q^{-1/3} lies in that range. It is a construction parameter, not fitted to any target quantity.
Threshold constants (14, 13, 4q) = 14 for arcs, 13 = 14 - 1, 4q for cliques
Chosen for convenience in Lemma 4.2; the paper states the constants are not optimized. The asymptotic Theta(t^2) claim is insensitive to these values, which only affect the lower-bound constant 1/832.

assumptions (4)

standard math Standard properties of the projective plane PG(2,q): q^2+q+1 points and lines, each line contains q+1 points, each point lies on q+1 lines, two points determine a unique line, two lines meet in a unique point (Lemma 2.3).
Used throughout Section 4 for degree counts, uniqueness of common neighbors, the arc argument, and the forced-incidence count in Lemma 4.2.
standard math Bertrand's postulate: for every sufficiently large real x there is a prime q with x <= q <= 2x.
Used in the proof of Theorem 1.1 to convert the q-indexed lower-bound construction into f_r(t) >= c t^2 for all sufficiently large t.
standard math Probabilistic method tools: independence of the Bernoulli incidence variables, linearity of expectation, Markov's inequality, and the union bound.
The whole proof of Lemma 4.2 is a probabilistic existence argument; independence is by construction since all xi(p,ell) are chosen independently.
domain assumption C4-freeness of the constructed graph Gamma_q (proven in Lemma 4.1) is needed for the mixed-clique bound in Theorem 4.3 and for the |F| <= 4*Delta bound in Lemma 5.2.
The uniqueness of the line through two points in PG(2,q) gives C4-freeness; the clique and family bounds in Sections 4 and 5 rely on this structural fact.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sharp quadratic $\chi$-binding functions for powers of bipartite graphs." pith.science (2026). https://pith.science/paper/HBLSOXXA

@misc{pith2026260827396,
  author       = {Pith},
  title        = {Pith review of: Sharp quadratic $\chi$-binding functions for powers of bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HBLSOXXA}},
  note         = {Machine review of arXiv:2608.27396}
}

abstract

For every natural number $r\geq 2$, we construct $r^{th}$ powers of bipartite graphs whose chromatic number is quadratic in their clique number, showing that the straightforward quadratic upper bound is best possible. We thereby settle an open problem posed by Chakraborty, Chandran, Jacob and Pillai [J. Graph Theory 112(3) (2026), 235-254] by establishing the sharpness of the quadratic bound for squares of bipartite graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Sunil and Jacob, Dalu and Pillai, Raji R

Chakraborty, Dibyayan and Chandran, L. Sunil and Jacob, Dalu and Pillai, Raji R. , title =. Journal of Graph Theory , volume =. doi:https://doi.org/10.1002/jgt.70014 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.70014 , year =

work page doi:10.1002/jgt.70014
[2]

Journal of Graph Theory , volume=

A survey of -boundedness , author=. Journal of Graph Theory , volume=. 2020 , publisher=

work page 2020
[3]

Kramer, Florica and Kramer, Horst , journal=. Ein F

work page
[4]

Un probleme de coloration des sommets d’un graphe , author=. CR Acad. Sci. Paris A , volume=

work page
[5]

Combinatorics, Probability and Computing , volume=

The chromatic number of graph powers , author=. Combinatorics, Probability and Computing , volume=. 2002 , publisher=

work page 2002
[6]

Cranston , title =

Daniel W. Cranston , title =. The Electronic Journal of Combinatorics , volume =. 2023 , note =. doi:10.37236/10898 , eprint =

work page doi:10.37236/10898 2023
[7]

Discrete Mathematics , volume =

Florica Kramer and Horst Kramer , title =. Discrete Mathematics , volume =. 2008 , doi =

work page 2008
[8]

Journal of Graph Theory , volume =

Alex Scott and Paul Seymour , title =. Journal of Graph Theory , volume =. 2020 , doi =

work page 2020

Show all 17 references

[9]

On the Chromatic Number of Powers of Subdivisions of Graphs , journal =

Michael Anastos and Simona Boyadzhiyska and Silas Rathke and Juanjo Ru. On the Chromatic Number of Powers of Subdivisions of Graphs , journal =. 2025 , doi =

2025
[10]

J. W. P. Hirschfeld , title =. 1998 , isbn =

1998
[11]

Spencer , title =

Noga Alon and Joel H. Spencer , title =. 2016 , isbn =

2016
[12]

Algorithmica , volume =

Hoang-Oanh Le and Van Bang Le , title =. Algorithmica , volume =. 2019 , doi =

2019
[13]

The Electronic Journal of Combinatorics , volume =

Seog-Jin Kim and Boram Park , title =. The Electronic Journal of Combinatorics , volume =. 2015 , doi =

2015
[14]

Coloring Powers of Planar Graphs , journal =

Geir Agnarsson and Magn. Coloring Powers of Planar Graphs , journal =. 2003 , doi =

2003
[15]

Acta Mathematica Sinica, English Series , volume =

Lian-Ying Miao and Yi-Zheng Fan , title =. Acta Mathematica Sinica, English Series , volume =. 2014 , doi =

2014
[16]

Random Structures & Algorithms , volume =

Mohammad Mahdian , title =. Random Structures & Algorithms , volume =. 2000 , doi =

2000
[17]

F. R. K. Chung and Andr. The Maximum Number of Edges in. Discrete Mathematics , volume =. 1990 , doi =

1990

Pith tools

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

[1] [1]

Sunil and Jacob, Dalu and Pillai, Raji R

Chakraborty, Dibyayan and Chandran, L. Sunil and Jacob, Dalu and Pillai, Raji R. , title =. Journal of Graph Theory , volume =. doi:https://doi.org/10.1002/jgt.70014 , url =. https://onlinelibrary.wiley.com/doi/pdf/10.1002/jgt.70014 , year =

work page doi:10.1002/jgt.70014

[2] [2]

Journal of Graph Theory , volume=

A survey of -boundedness , author=. Journal of Graph Theory , volume=. 2020 , publisher=

work page 2020

[3] [3]

Kramer, Florica and Kramer, Horst , journal=. Ein F

work page

[4] [4]

Un probleme de coloration des sommets d’un graphe , author=. CR Acad. Sci. Paris A , volume=

work page

[5] [5]

Combinatorics, Probability and Computing , volume=

The chromatic number of graph powers , author=. Combinatorics, Probability and Computing , volume=. 2002 , publisher=

work page 2002

[6] [6]

Cranston , title =

Daniel W. Cranston , title =. The Electronic Journal of Combinatorics , volume =. 2023 , note =. doi:10.37236/10898 , eprint =

work page doi:10.37236/10898 2023

[7] [7]

Discrete Mathematics , volume =

Florica Kramer and Horst Kramer , title =. Discrete Mathematics , volume =. 2008 , doi =

work page 2008

[8] [8]

Journal of Graph Theory , volume =

Alex Scott and Paul Seymour , title =. Journal of Graph Theory , volume =. 2020 , doi =

work page 2020