The chromatic-polynomial characterization of signed complete graphs

From papers

Let Σ1\Sigma_1 and Σ2\Sigma_2 be signed complete graphs. Write Σ1Σ2\Sigma_1\cong\Sigma_2 when they are isomorphic, and let B(Σ,x,y)\mathscr B(\Sigma,x,y) and E(Σ,x,y)\mathsf E(\Sigma,x,y) denote their bivariate and ordinary chromatic polynomials, respectively. Signed complete-graph characterization conjecture.

Σ1Σ2    B(Σ1,x,y)=B(Σ2,x,y)    E(Σ1,x,y)=E(Σ2,x,y).\Sigma_1 \cong \Sigma_2 \iff \mathscr B(\Sigma_1,x,y) = \mathscr B(\Sigma_2,x,y) \iff \mathsf E(\Sigma_1,x,y) = \mathsf E(\Sigma_2,x,y).

Thus, within signed complete graphs, both polynomials are conjectured to determine the graph up to isomorphism. The source gives this as a conjecture and does not provide a resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Gary R. W. Greaves, Jeven Syatriadi and Charissa I. Utomo, “Chromatic polynomials of signed graphs and dominating-vertex deletion formulae”, arXiv:2407.00883 (2024).

Solutions 0

No solutions have been posted yet.