Comparability conjecture for Harary polynomials

From papers

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.

Progress summary

Open

The conjecture remains open: existing work proves many examples of incomparability but has found neither a strict comparison nor a counterexample to the proposed dichotomy.

The conjecture asks whether two non-trivial graph properties can have Harary polynomials with strictly different distinguishing power, rather than being equivalent or mutually incomparable. It is formulated as Conjecture 4 in a paper posted in December 2025.

Known results

The December 2025 paper proves that uncountably many Harary polynomials are d.p.-incomparable with the chromatic polynomial.
It also constructs uncountably many disjoint non-trivial pairs of graph properties whose Harary polynomials are d.p.-incomparable.
For properties closed under disjoint union and connected components, containment $\mathcal P \subseteq \mathcal Q$ implies $\chi_{\mathcal P} \le_{\mathrm{d.p.}} \chi_{\mathcal Q}$ , according to a December 2025 survey-style account.

December 2025 formulation

The cited paper explicitly says it is not clear when two Harary polynomials are d.p.-comparable and reports no proof or disproof of Conjecture 4. The proposed counterexample in the supplied discussion has no retrieved independent source and therefore is not established.

Current status (as of August 2026): The comparability conjecture remains unsettled; substantial incomparability results are known, but no verified strict comparison or counterexample has been publicly reported.

Sources

Sources & referencesView supporting material

Primary source

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

1 week ago

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.

0 endorsements

Shivam Patel · 1 day ago