arxiv: 2604.14006 · v1 · submitted 2026-04-15 · 🧮 math.CO

Recognition: unknown

Coloring powers of random graphs

Alan Frieze , Ross Kang , Aditya Raut , Michelle Sweering , Hilde Verbeek

Authors on Pith no claims yet

Pith reviewed 2026-05-10 12:44 UTC · model grok-4.3

classification 🧮 math.CO

keywords random graphsgraph powersmaximum degreechromatic numberasymptotic boundsbinomial modelsparse regimedense regime

0 comments

The pith

The rth power of a sparse random graph has maximum degree asymptotically log n over the (r+1)th iterated logarithm, with chromatic number bounded by the maximum degrees of its floor(r/2)th and (r-1)th powers.

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

The paper determines the typical maximum degree and chromatic number of the rth power of the binomial random graph G(n,p). In the sparse regime with fixed average degree d, it proves the maximum degree concentrates at log n divided by the (r+1)th iterated logarithm. It also shows the chromatic number lies between one plus the maximum degree of the floor(r/2)th power and one plus the maximum degree of the (r-1)th power, with equality in the upper bound when r equals 2. A reader would care because these quantities describe how longer-range connections reshape connectivity and colorability in random networks. In denser regimes where d grows faster than log n but stays below n to the power 1/r minus a constant, the chromatic number is shown to be on the order of d to the r over its logarithm.

Core claim

Given a graph G and integer r at least 1, the rth power G^r adds edges between all pairs at distance at most r. For G equal to the binomial random graph G(n,p) with p equal to d over n and d a fixed constant, the paper proves that with high probability the maximum degree satisfies Delta(G(n,p)^r) asymptotically equivalent to log n over log base (r+1) of n. It further proves that Delta(G(n,p) to the floor(r/2)) plus one is at most the chromatic number of G(n,p)^r, which is at most Delta(G(n,p) to the (r-1)) plus one, and that the upper bound is tight for r equal to 2. When d grows faster than log n yet stays at most n to the power 1/r minus Omega of 1, the chromatic number is Theta of d to r,

What carries the argument

The rth power graph construction on G(n,p), whose maximum degree is set by the number of vertices reachable in at most r steps and whose chromatic number is controlled by greedy coloring bounds from the maximum degrees of lower powers.

If this is right

With high probability the maximum degree of G(n,p)^r follows the iterated-logarithm formula for any fixed r in the sparse regime.
The chromatic number of the rth power is at most one more than the maximum degree of the (r-1)th power.
When r equals 2 the chromatic number of the square equals exactly the maximum degree of the original graph plus one.
In the denser regime the chromatic number grows as Theta(d^r over log d).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same neighborhood-counting approach might yield analogous degree formulas for other distance-based graph operations such as distance graphs.
Numerical checks on moderate-sized instances could reveal the speed of convergence to the asymptotic formulas.
The bounds may suggest efficient coloring heuristics for powered random graphs by first coloring the underlying sparse graph.

Load-bearing premise

The binomial random graph G(n,p) in the given density ranges produces typical neighborhood sizes that yield the stated concentration for degrees in the powered graph.

What would settle it

Simulate a single large instance of G(n,p) with n around 10^6 and fixed d, compute the actual maximum degree in its rth power, and check whether it stays within a small constant factor of log n over the (r+1)th iterated log; a consistent large deviation would falsify the main degree claim.

read the original abstract

Given a graph $G$ and an integer $r\ge 1$, the $r$th power $G^r$ of $G$ is the graph obtained from $G$ by adding edges for all pairs of distinct vertices at distance at most $r$ from each other. We focus on two basic structural properties of the $r$th power of the binomial random graph $G_{n,p}$, namely, the maximum degree $\Delta(G_{n,p}^r)$ and the chromatic number $\chi(G_{n,p}^r)$, and give with high probability (w.h.p.) bounds. In the sparse case that $p=d/n$ for some fixed constant $d>0$, we prove the following. We prove that w.h.p.~$\Delta(G_{n,p}^r) \sim \frac{\log n}{\log_{(r+1)}n}$ (where $\log_{(1)}n=\log n$ and $\log_{(r+1)}n=\log\log_{(r)}n$) and that w.h.p.~$\Delta(G_{n,p}^{\lfloor{r/2}\rfloor})+1 \le \chi(G_{n,p}^r) \le \Delta(G_{n,p}^{r-1})+1$. For $r=2$, we show the upper bound holds with equality. For denser cases, for $d$ satisfying $d=\omega(\log n)$ and $d\le n^{1/r-\Omega(1)}$ as $n\to\infty$, we have $\chi(G_{n,p}^r) = \Theta(d^r/\log d)$ w.h.p.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down w.h.p. bounds on max degree and chromatic number for r-powers of G(n,p) using iterated logs in the sparse regime and a Theta form when d grows.

read the letter

The main things to know are the asymptotic for Delta(G_{n,p}^r) ~ log n / log_{(r+1)} n when p=d/n is constant, plus the sandwich Delta(floor(r/2) power) +1 ≤ chi(G^r) ≤ Delta((r-1) power) +1 with equality at r=2, and the Theta(d^r / log d) for chi when d is between omega(log n) and n to a power below 1/r. These organize the behavior across regimes in a way that extends the classic chi ~ d/log d picture for plain random graphs. The iterated-log form and the cross-power relations for the chromatic bounds look new; earlier random-graph coloring work did not state these exact relations. The denser-case asymptotic follows naturally once you view the power as an inhomogeneous graph with effective degree d^r, so that part aligns with known techniques. The paper does well by leaning on the local tree-like structure of G(n,p) to control neighborhoods and cliques in the powers, which keeps the arguments grounded rather than hand-wavy. The lower bound from radius-floor(r/2) balls is standard but applied cleanly here. The upper bound strengthens the usual greedy estimate in a plausible way. Soft spots are minor and mostly about the restricted ranges for d, which are chosen to stay away from the complete-graph threshold and the very dense regime; that is necessary but means the results do not cover all p. Concentration and error terms for the degree bound would need the usual careful second-moment work, but nothing in the abstract or stress-test suggests a load-bearing gap. The claims are internally consistent with the G(n,p) model. This is for combinatorial probabilists who already know the basic random-graph coloring results and want the extension to distance-r graphs. A reader working on powers, distance graphs, or inhomogeneous models would get direct use from the bounds. It deserves a serious referee because the statements are precise, the regimes are natural, and the authors have the expertise to carry the proofs through.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the maximum degree and chromatic number of the r-th power G^r of the binomial random graph G_{n,p}. In the sparse regime p = d/n with fixed d > 0, it proves w.h.p. that Δ(G_{n,p}^r) ∼ log n / log_{(r+1)} n (with the iterated logarithm defined recursively), together with the sandwich Δ(G_{n,p}^{⌊r/2⌋}) + 1 ≤ χ(G_{n,p}^r) ≤ Δ(G_{n,p}^{r-1}) + 1; equality holds in the upper bound when r = 2. In the denser regime d = ω(log n) and d ≤ n^{1/r − Ω(1)}, it establishes χ(G_{n,p}^r) = Θ(d^r / log d) w.h.p.

Significance. If the claims hold, the work supplies precise, parameter-free asymptotics for the maximum degree of random-graph powers in the sparse regime and tight chromatic-number bounds that exploit the local tree-like geometry and ball-clique structure. The denser-regime result aligns with known inhomogeneous-random-graph chromatic-number asymptotics. These are natural and useful extensions of classical G(n,p) results; the explicit matching of lower and upper bounds for r = 2 is a particular strength.

minor comments (3)

The definition of the iterated logarithm log_{(r+1)} n is given only in the abstract; it should be restated at the beginning of the sparse-case section for self-contained reading.
In the statement of the denser regime, the hidden constant inside the Ω(1) in the upper bound on d should be made explicit (or at least bounded) so that the precise range of validity is clear.
The proof sketch for the lower bound χ(G^r) ≥ Δ(G^{⌊r/2⌋}) + 1 relies on the existence of a clique formed by a maximum ball of radius ⌊r/2⌋; a short paragraph confirming that the diameter argument survives the random-graph local structure would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results on the maximum degree and chromatic number of powers of random graphs, and for recommending minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained in G(n,p) model

full rationale

The paper establishes w.h.p. bounds on Δ(G_{n,p}^r) and χ(G_{n,p}^r) via direct probabilistic analysis of the binomial random graph. The lower bound χ(G^r) ≥ Δ(G^{⌊r/2⌋})+1 follows from the structural fact that radius-⌊r/2⌋ balls induce cliques in the power graph (diameter ≤ r). The upper bound exploits the locally tree-like structure of G(n,p) for a strengthened greedy coloring. The Θ(d^r/log d) asymptotic in the denser regime matches standard results for inhomogeneous random graphs with effective degree Θ(d^r). No equations reduce claims to fitted parameters, self-definitions, or load-bearing self-citations; all steps are independent consequences of the stated G(n,p) regimes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard binomial random-graph model and classical concentration tools; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Binomial random graph G(n,p) model with the given p regimes
Invoked throughout the abstract as the underlying probability space.

pith-pipeline@v0.9.0 · 5601 in / 1262 out tokens · 46971 ms · 2026-05-10T12:44:47.943971+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
cs.DS 2026-05 unverdicted novelty 7.0

Online algorithms achieve multiplicative approximation r^{1/(r-1)} for maximum independent sets in dense r-uniform ER hypergraphs and (max γ_i)^{-1/(r-1)} for balanced sets in r-partite versions, with matching lower bounds.

Reference graph

Works this paper leans on

30 extracted references · 2 canonical work pages · cited by 1 Pith paper

[1]

Achlioptas and A

D. Achlioptas and A. Naor. The two possible values of the chromatic number of a random graph.Ann. of Math. (2), 162(3):1335–1351, 2005

2005
[2]

Addario-Berry, N

L. Addario-Berry, N. Broutin, and C. Goldschmidt. The continuum limit of critical random graphs.Probab. Theory Related Fields, 152(3-4):367–406, 2012

2012
[3]

Agnarsson and M

G. Agnarsson and M. M. Halld´ orsson. Coloring powers of planar graphs.SIAM J. Discrete Math., 16(4):651–662, 2003

2003
[4]

N. Alon, M. Krivelevich, and B. Sudakov. Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Series B, 77(1):73–82, 1999

1999
[5]

Alon and B

N. Alon and B. Mohar. The chromatic number of graph powers.Combinatorics, Probability and Computing, 11(1):1–10, 2002

2002
[6]

Amini, L

O. Amini, L. Esperet, and J. van den Heuvel. A unified approach to distance-two colouring of graphs on surfaces.Combinatorica, 33(3):253–296, 2013

2013
[7]

Atkinson and A

G. Atkinson and A. Frieze. On the-independence number of sparse random graphs. Combinatorics, Probability and Computing, 13(3):295–309, 2004. 14

2004
[8]

P. Ayre, A. Coja-Oghlan, and C. Greenhill. Lower bounds on the chromatic number of random graphs.Combinatorica, 42(5):617–658, 2022

2022
[9]

Bollob´ as

B. Bollob´ as. The distribution of the maximum degree of a random graph.Discrete Math., 32(2):201–203, 1980

1980
[10]

Bollob´ as

B. Bollob´ as. The diameter of random graphs.Trans. Amer. Math. Soc., 267(1):41–52, 1981

1981
[11]

Bollob´ as

B. Bollob´ as. The chromatic number of random graphs.Combinatorica, 8(1):49–55, 1988

1988
[12]

Coja-Oghlan and D

A. Coja-Oghlan and D. Vilenchik. The chromatic number of random graphs for most average degrees.Int. Math. Res. Not. IMRN, (19):5801–5859, 2016

2016
[13]

Graph structure via local occupancy,https://arxiv.org/abs/2003.14361 (preprint), 2020 (cit

E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. Graph structure via local occupancy. arXiv e-prints, page arXiv:2003.14361, Mar. 2020

work page arXiv 2003
[14]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On the evolution of random graphs.Magyar Tud. Akad. Mat. Kutat´ o Int. K¨ ozl., 5:17–61, 1960

1960
[15]

Frieze and M

A. Frieze and M. Karo´ nski.Introduction to random graphs. Cambridge University Press, Cambridge, 2016

2016
[16]

Frieze and A

A. Frieze and A. Raut. A note on the chromatic number of the square of a sparse random graph, 2023

2023
[17]

Garapaty, D

K. Garapaty, D. Lokshtanov, H. K. Maji, and A. Pothen. The chromatic number of squares of random graphs.Journal of Combinatorics, 14(4):507–537, 2023

2023
[18]

Havet, J

F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed. List Colouring Squares of Planar Graphs.arXiv e-prints, page arXiv:0807.3233, July 2008

work page arXiv 2008
[19]

S. Janson. Poisson approximation for large deviations.Random Structures Algorithms, 1(2):221–229, 1990

1990
[20]

R. J. Kang and C. McDiarmid. Colouring random graphs. InTopics in chromatic graph theory, volume 156 ofEncyclopedia Math. Appl., pages 199–229. Cambridge Univ. Press, Cambridge, 2015

2015
[21]

R. J. Kang and F. Pirot. Coloring powers and girth.SIAM J. Discrete Math., 30(4):1938–1949, 2016

1938
[22]

R. J. Kang and F. Pirot. Distance colouring without one cycle length.Combin. Probab. Comput., 27(5):794–807, 2018

2018
[23]

R. J. Kang and W. van Loon. Tree-like distance colouring for planar graphs of sufficient girth.Electron. J. Combin., 26(1):Paper No. 1.23, 15, 2019. 15

2019
[24]

Klee and D

V. Klee and D. Larman. Diameters of random graphs.Can. J. Math., 33:618–640, 1981

1981
[25]

N. Linial. Locality in distributed graph algorithms.SIAM J. Comput., 21(1):193–201, 1992

1992
[26]

T. Luczak. The chromatic number of random graphs.Combinatorica, 11(1):45–54, 1991

1991
[27]

Matula and L

D. Matula and L. Kuˇ cera. An expose-and-merge algorithm and the chromatic number of a random graph. InRandom graphs ’87 (Pozna´ n, 1987), pages 175–187. Wiley, Chichester, 1990

1987
[28]

D. W. Matula. Expose-and-merge exploration and the chromatic number of a random graph.Combinatorica, 7(3):275–284, 1987

1987
[29]

Pokrovskiy

A. Pokrovskiy. Edge growth in graph powers.Australas. J. Combin., 58:347–357, 2014

2014
[30]

Riordan and N

O. Riordan and N. Wormald. The diameter of sparse random graphs.Combin. Probab. Comput., 19(5-6):835–926, 2010. 16

2010