Comparability conjecture for Harary polynomials

About 1 year old · traced to 2025

Let ${\mathcal P}$ and ${\mathcal Q}$ be non-trivial graph properties, and let $\chi_{\mathcal P}$ and $\chi_{\mathcal Q}$ be their Harary polynomials. Two graph polynomials are d.p.-equivalent when they distinguish exactly the same pairs of graphs, while they are d.p.-incomparable when neither distinguishes at least all pairs distinguished by the other.

Harary-polynomial comparability conjecture. Either $\chi_{\mathcal P}$ and $\chi_{\mathcal Q}$ are d.p.-equivalent or they are d.p.-incomparable.

The conjecture asserts that two Harary polynomials cannot have a strict one-way distinguishability comparison. The supplied text does not state whether this has been resolved.

References

Primary source

Johann A. Makowsky, “Distinctive power and comparability of Harary polynomial”, arXiv:2512.22556 (2025).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A proposed counterexample claims the conjecture is false, but the only supporting argument is unverified and the latest paper records no solution.

The conjecture asserts that Harary polynomials of any two non-trivial graph properties are either d.p.-equivalent or d.p.-incomparable, ruling out strict one-way distinguishability. Johann A. Makowsky formulated it as Conjecture 4 in December 2025.

December 2025 preprint

Makowsky reports that the criteria for d.p.-comparability are unclear. The paper proves uncountably many examples of incomparability, including with the chromatic polynomial, but gives neither a strict comparison nor a disproof of the conjecture.

Posted attempt

A proposed construction takes $\mathcal P=\{\varnothing\}\cup\{G:|V(G)|\text{ is odd}\}$ and $\mathcal Q$ as the edgeless-graph property. It claims $\chi_{\mathcal P}\leq_{\mathrm{d.p.}}\chi_{\mathcal Q}$ strictly, using graph order detected by the monic chromatic polynomial, and therefore claims a complete counterexample. The argument has not been independently verified.

Current status (as of August 2026): The conjecture has no verified resolution; a posted complete-counterexample claim exists, while the published preprint still provides only incomparability results.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

Let

\mathcal P=\{\varnothing\}\cup \{G:|V(G)|\text{ is odd}\},

and let $\mathcal Q$ be the class of all edgeless graphs. Both are infinite proper graph properties, and hence both are nontrivial in the sense of the conjecture.

A $\mathcal P$ -coloring of an $n$ -vertex graph is exactly a coloring for which every nonempty color class has odd cardinality. This condition is independent of the edges. Consequently,

\chi_{\mathcal P}(G;k) =n![t^n](1+\sinh t)^k =:F_n(k), \qquad n=|V(G)|.

On the other hand, a $\mathcal Q$ -coloring is precisely a proper coloring, so

\chi_{\mathcal Q}(G;k)=\chi_G(k),

the ordinary chromatic polynomial.

Because $\chi_G(k)$ is monic of degree $|V(G)|$ ,

\chi_{\mathcal Q}(G;k)=\chi_{\mathcal Q}(H;k) \Longrightarrow |V(G)|=|V(H)| \Longrightarrow \chi_{\mathcal P}(G;k)=\chi_{\mathcal P}(H;k).

Therefore

\chi_{\mathcal P}\le_{\mathrm{d.p.}}\chi_{\mathcal Q}.

This comparison is strict. For the edgeless graph $E_2$ and the complete graph $K_2$ ,

\chi_{\mathcal P}(E_2;k) =\chi_{\mathcal P}(K_2;k) =k(k-1),

whereas

\chi_{\mathcal Q}(E_2;k)=k^2, \qquad \chi_{\mathcal Q}(K_2;k)=k(k-1).

Thus these Harary polynomials are comparable but not equivalent.

Moreover, both $E_2$ and $K_2$ are chromatically unique, whereas neither is $\chi_{\mathcal P}$ -unique. Hence the same counterexample applies when distinguishing-power equivalence is formulated through the sets of uniquely determined graphs. The proposed dichotomy is therefore false.