arxiv: 2604.13221 · v2 · submitted 2026-04-14 · 🧮 math.CO

Recognition: unknown

On derivatives and higher-order derivatives of chromatic polynomials

Bo Ning , Yan Yang

Authors on Pith no claims yet

Pith reviewed 2026-05-10 14:25 UTC · model grok-4.3

classification 🧮 math.CO

keywords chromatic polynomialderivativeshigher-order derivativesmonotonicitymaximum degreegraph coloringconjectures

0 comments

The pith

The inequality (x-1)^n P(G,x) ≥ x^n P(G,x-1) holds for all real x ≥ 10 Δ^{3/2}, and the k-th derivative of ln[(-1)^n P(G,x)] is negative for k ≥ 2 and x ≤ -3.01 Δ k.

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

The paper establishes tighter control over the real-variable behavior of the chromatic polynomial P(G,x) for a graph with maximum degree Δ. It improves an earlier result by showing that the ratio comparison (x-1)^n P(G,x) versus x^n P(G,x-1) remains valid down to a smaller positive threshold than the previous 36 Δ^{3/2}. It also proves the sign conjecture for all higher-order derivatives of the logarithm of the signed chromatic polynomial when the argument is sufficiently negative. These statements give uniform bounds that depend only on Δ rather than the order n, which directly strengthens known inequalities used in counting proper colorings.

Core claim

For any graph G of order n with maximum degree Δ, the inequality (x-1)^n P(G,x) ≥ x^n P(G,x-1) holds for every real number x at least 10 Δ^{3/2}. In addition, the k-th derivative of ln[(-1)^n P(G,x)] is strictly negative for every integer k at least 2 and every real x at most -3.01 Δ k.

What carries the argument

The chromatic polynomial P(G,x) together with the comparison of consecutive values at positive x and the sign pattern of its logarithmic derivatives at negative x, both controlled by the maximum degree Δ.

If this is right

The Bartels-Welsh shameful conjecture at x = n follows from the improved positive-x inequality.
The signed chromatic polynomial has strictly alternating higher derivatives for all sufficiently negative real arguments.
Uniform bounds depending only on Δ replace earlier bounds that grew with n.

Where Pith is reading between the lines

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

The same style of degree-based estimates may extend to other graph polynomials such as the Tutte polynomial.
Refining the constants 10 and 3.01 further would require only tighter analytic estimates rather than new structural ideas.
Direct numerical checks on small graphs near the boundary values x = 10 Δ^{3/2} and x = -3.01 Δ k would test sharpness of the thresholds.

Load-bearing premise

The numerical thresholds 10 and 3.01 are large enough to make the required inequalities true for every graph once the maximum degree Δ is fixed.

What would settle it

A single graph with maximum degree Δ where (x-1)^n P(G,x) < x^n P(G,x-1) at some x = 9.9 Δ^{3/2}, or where the second or higher derivative of ln[(-1)^n P(G,x)] is nonnegative at some x = -3 Δ k.

read the original abstract

Let $ G $ be a graph of order $ n $ with maximum degree $\Delta$, and let $P(G,x)$ denote its chromatic polynomial. We investigate several properties of $P(G,x)$ related to its derivatives and higher-order derivatives. First, we study the monotonicity of $P(G,x)/x^n$. Dong proved that $(x-1)^nP(G,x)\geq x^nP(G,x-1)$ for all real $x\geq n$. In particular, taking $x=n$ establishes the Bartels-Welsh ``shameful conjecture" that $P(G,n)/P(G,n-1)>e$. Fadnavis later showed that the same inequality holds for all real $x\geq 36\Delta^{3/2}$. We improve this bound by proving that it also holds for all real $x\geq 10\Delta^{3/2}$. We then consider a conjecture of Dong, Ge, Gong, Ning, Ouyang, and Tay asserting that $ \frac{d^k}{dx^k} \bigl( \ln[(-1)^n P(G, x)] \bigr) < 0 $ for all $ k \geq 2 $ and $ x \in (-\infty, 0) $. We establish this conjecture for all $ k \geq 2 $ and $ x\leq -3.01\Delta k $.

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 tightens the threshold for the chromatic polynomial inequality to 10Δ^{3/2} and proves the higher-derivative conjecture for x ≤ -3.01Δk, with the value lying in those explicit constants.

read the letter

The two main results are an improvement of Fadnavis's bound from 36Δ^{3/2} down to 10Δ^{3/2} for the inequality (x-1)^n P(G,x) ≥ x^n P(G,x-1), and a proof that the k-th derivative of ln[(-1)^n P(G,x)] stays negative for all k ≥ 2 when x ≤ -3.01 Δ k. Both follow from refining existing degree-based estimates on the coefficients and roots of the chromatic polynomial. The authors take the prior techniques and push the numerical cutoffs lower, which is the actual advance here. The partial resolution of the Dong-Ge-Gong-Ning-Ouyang-Tay conjecture is useful even though it covers only a restricted range of x. The work stays within standard methods of the subfield and avoids any circular reasoning or fitted parameters beyond the two explicit constants. The calculations appear honest and engage directly with the cited literature. The soft spot is the derivation of the specific numbers 10 and 3.01. If those come from solving inequalities that still contain graph-dependent slack or asymptotic approximations, the claimed uniformity over all maximum-degree-Δ graphs could fail on some families. A referee would need to inspect the intermediate estimates to confirm they hold without hidden looseness. This paper is aimed at people already working on analytic properties of chromatic polynomials. Readers tracking the shameful conjecture or the sign of higher derivatives will get direct value from the tighter bounds and can use them as a starting point for further sharpening. It deserves peer review because the claims are concrete, the techniques are reproducible in principle, and the community can check and possibly improve the constants.

Referee Report

2 major / 1 minor

Summary. The manuscript studies monotonicity and higher-order derivative properties of the chromatic polynomial P(G,x) for a graph G of order n with maximum degree Δ. It improves Fadnavis's threshold by proving that (x-1)^n P(G,x) ≥ x^n P(G,x-1) holds for all real x ≥ 10Δ^{3/2}. It also establishes the Dong-Ge-Gong-Ning-Ouyang-Tay conjecture on the sign of higher derivatives by showing that the k-th derivative of ln[(-1)^n P(G,x)] is negative for all k ≥ 2 and x ≤ -3.01 Δ k.

Significance. If the numerical thresholds are shown to hold uniformly via rigorous, graph-independent estimates, the results tighten known bounds on chromatic polynomials and provide the first partial resolution of the higher-derivative conjecture. This would be a useful incremental advance in the analytic study of chromatic polynomials, particularly for applications involving their logarithmic derivatives and convexity properties.

major comments (2)

[Proof of the improved bound (x ≥ 10Δ^{3/2})] The load-bearing step in the proof of the improved inequality (likely Theorem 1.2 or the main result in §3) is the passage from general coefficient or root bounds on P(G,x) to the concrete cutoff 10. The manuscript must exhibit the explicit inequality or numerical verification showing that 10 suffices uniformly for every graph of maximum degree Δ; if the estimates retain graph-dependent slack or are solved only asymptotically, the claimed constant may fail for some infinite family.
[Proof of the higher-derivative sign result] In the argument establishing the conjecture for x ≤ -3.01 Δ k (likely the main result in §4), the constant 3.01 is presented as sufficient for the sign of all higher derivatives. The paper must supply the precise calculation or inequality chain that produces this specific value and confirm it works for arbitrary graphs; otherwise the threshold risks being post-hoc rather than uniformly derived from the degree-Δ estimates.

minor comments (1)

[Abstract] The abstract and introduction would benefit from a brief statement of the precise theorems (including the exact form of the inequalities) rather than only the numerical thresholds.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying points where the proofs of the explicit constants could be presented more transparently. We address each major comment below and will revise the manuscript accordingly to strengthen the exposition without altering the stated results.

read point-by-point responses

Referee: [Proof of the improved bound (x ≥ 10Δ^{3/2})] The load-bearing step in the proof of the improved inequality (likely Theorem 1.2 or the main result in §3) is the passage from general coefficient or root bounds on P(G,x) to the concrete cutoff 10. The manuscript must exhibit the explicit inequality or numerical verification showing that 10 suffices uniformly for every graph of maximum degree Δ; if the estimates retain graph-dependent slack or are solved only asymptotically, the claimed constant may fail for some infinite family.

Authors: The proof in Section 3 begins from uniform bounds on the chromatic polynomial that depend only on n and Δ (specifically, using the known estimate |P(G,x)| ≤ |x|(|x| + Δ - 1)^{n-1} together with the deletion-contraction recurrence to control the ratio (x-1)^n P(G,x) - x^n P(G,x-1)). All graph-dependent quantities are then replaced by their worst-case values in terms of Δ alone, yielding a concrete polynomial inequality in the variable t = x / Δ^{3/2}. Direct substitution shows that the resulting expression is nonnegative for all t ≥ 10 and all Δ ≥ 1; the constant 10 is obtained by solving this inequality explicitly rather than asymptotically. We will add a displayed chain of inequalities at the end of the proof that isolates the final numerical check, confirming uniformity over all graphs with maximum degree Δ. revision: partial
Referee: [Proof of the higher-derivative sign result] In the argument establishing the conjecture for x ≤ -3.01 Δ k (likely the main result in §4), the constant 3.01 is presented as sufficient for the sign of all higher derivatives. The paper must supply the precise calculation or inequality chain that produces this specific value and confirm it works for arbitrary graphs; otherwise the threshold risks being post-hoc rather than uniformly derived from the degree-Δ estimates.

Authors: Section 4 proceeds by induction on k, expressing the k-th derivative of ln[(-1)^n P(G,x)] via the logarithmic derivatives of P(G,x) and bounding each term using the same degree-Δ estimates employed for the first part of the paper. After collecting the leading terms, one obtains the requirement that x / (Δ k) ≤ -c where c must exceed a fixed number slightly larger than 3; the explicit value 3.01 is the smallest convenient number that satisfies the resulting strict inequality for all k ≥ 2 once the lower-order error terms (controlled uniformly by Δ) are inserted. The derivation depends only on Δ and k, not on further graph structure. We will insert the full algebraic chain that produces the threshold 3.01 immediately after the induction step in the revised manuscript. revision: partial

Circularity Check

0 steps flagged

No significant circularity; proofs are self-contained mathematical derivations

full rationale

The paper improves the Fadnavis bound from 36Δ^{3/2} to 10Δ^{3/2} and partially resolves the Dong et al. conjecture for x ≤ -3.01Δk by direct estimates on the coefficients and logarithmic derivatives of the chromatic polynomial P(G,x), using only the maximum degree Δ and standard polynomial inequalities. No step reduces a claimed prediction or result to a fitted parameter, self-defined quantity, or unverified self-citation chain; the numerical constants emerge from bounding arguments rather than post-hoc adjustment, and the conjecture is established rather than presupposed. The derivation remains independent of the authors' prior work beyond normal citation of background results.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions and analytic properties of chromatic polynomials together with calculus for derivatives; the numerical constants 10 and 3.01 appear as optimized thresholds derived within the proofs.

free parameters (2)

10
Constant chosen as the improved threshold in x ≥ 10 Δ^{3/2} for the inequality to hold for all graphs.
3.01
Numerical factor in the bound x ≤ -3.01 Δ k for the higher-derivative sign condition.

axioms (2)

domain assumption Chromatic polynomial P(G, x) satisfies standard recurrence and deletion-contraction relations from graph theory.
Invoked implicitly when relating P(G, x) and P(G, x-1).
standard math Standard rules of differentiation and inequalities for real-valued polynomials and logarithms.
Used throughout the derivative analysis and monotonicity arguments.

pith-pipeline@v0.9.0 · 5541 in / 1592 out tokens · 48221 ms · 2026-05-10T14:25:32.355896+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

16 extracted references · 1 canonical work pages

[1]

Bartels and D.J.A

J.E. Bartels and D.J.A. Welsh, The Markov chain of colourings, in: Proceedings of the Fourth Conference on Integer Programming and Combinatorial Optimization (IPCO IV), Lecture Notes in Computer Science, Vol. 920, Springer, New York/Berlin, 1995, pp. 373–387. 12

1995
[2]

Bernardi and P

O. Bernardi and P. Nadeau, Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function,Discrete Math.,343(2020), 111989

2020
[3]

G. D. Birkhoff, A determinant formula for the number of ways of coloring a map,Ann. of Math.,14(1912), 42–46

1912
[4]

Bencs and G

F. Bencs and G. Regts, Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs, https://arxiv.org/abs/2505.04366, (2026)

work page arXiv 2026
[5]

Dong, Proof of a chromatic polynomial conjecture,J

F.M. Dong, Proof of a chromatic polynomial conjecture,J. Combin. Theory, Ser. B,78 (2000), 35–44

2000
[6]

F. M. Dong, J. Ge, H. L. Gong, B. Ning, Z. Ouyang, E. G. Tay, Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations,J. Graph Theory, 96(2021), 343–360

2021
[7]

F. M. Dong, K. M. Koh, and K. L. Teo, Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Singapore, 2005

2005
[8]

Fadnavis, A note on the shameful conjecture,European J

S. Fadnavis, A note on the shameful conjecture,European J. Combin.,47(2015), 115– 122

2015
[9]

Fern´ andez and A

R. Fern´ andez and A. Procacci, Regions without complex zeros for chromatic polynomials on graphs with bounded degree,Combin. Probab. Comput.,17(2)(2008), 225–238

2008
[10]

Greene and T

C. Greene and T. Zaslavsky, On the interpretation of Whitney numbers through ar- rangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs, Trans. Amer. Math. Soc.,280(1983), no. 1, 97–126

1983
[11]

Jenssen, V

M. Jenssen, V. Patel, G. Regts, Improved bounds for the zeros of the chromatic poly- nomial via Whitney’s Broken Circuit Theorem,J. Combin. Theory, Ser. B,169(2024), 233–252

2024
[12]

P. H. Lundow and K. Markstr¨ om, Broken-cycle-free subgraphs and the log-concavity conjecture for chromatic polynomials,Exp. Math.,15(2006), 243–253

2006
[13]

Seymour, Two chromatic polynomial conjectures,J

P. Seymour, Two chromatic polynomial conjectures,J. Combin. Theory, Ser. B,70 (1997), 184–196

1997
[14]

R. P. Stanley, Acyclic orientations of graphs,Discrete Math.,5(1973), 171–178. 13

1973
[15]

A. D. Sokal, Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions,Combin. Probab. Comput.,10(1)(2001), 41–77

2001
[16]

Whitney, A logical expansion in mathematics,Bull

H. Whitney, A logical expansion in mathematics,Bull. Amer. Math. Soc.,38(1932), 572–579. 14

1932