The signed-threshold conjecture for bivariate chromatic polynomials

For each integer n0n\geqslant 0 and each vector a{1,0,1}n\bm{a}\in\{-1,0,1\}^n, let Ta\mathcal{T}_{\bm{a}} be the associated signed threshold graph, with bivariate chromatic polynomial B(Ta,x,y)\mathscr B(\mathcal{T}_{\bm{a}},x,y) and chromatic polynomial E(Ta,x,y)\mathsf E(\mathcal{T}_{\bm{a}},x,y). Signed-threshold conjecture. Let n0n \geqslant 0 be an integer and let a,b{1,0,1}n\bm{a}, \bm{b} \in \{-1,0,1\}^n. Then

a=b    Ta=Tb    B(Ta,x,y)=B(Tb,x,y)    E(Ta,x,y)=E(Tb,x,y).\bm{a} = \bm{b} \iff \mathcal{T}_{\bm{a}} = \mathcal{T}_{\bm{b}} \iff \mathscr B(\mathcal{T}_{\bm{a}},x,y) = \mathscr B(\mathcal{T}_{\bm{b}},x,y) \iff \mathsf E(\mathcal{T}_{\bm{a}},x,y) = \mathsf E(\mathcal{T}_{\bm{b}},x,y).

The conjecture extends an established result for the parameter sets {0,1}n{±1}n\{0,1\}^n\cup\{\pm1\}^n to {1,0,1}n\{-1,0,1\}^n. The source reports computational verification through n=12n=12, but the general assertion remains open.

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.