Chromatic-polynomial separation conjecture for signed Petersen graphs

About 13 years old · traced to

Let PP be the Petersen graph, let σ\sigma range over its sign functions, and write χ(P,σ)(k)\chi_{(P,\sigma)}(k) and χ(P,σ)∗(k)\chi^*_{(P,\sigma)}(k) for the numbers of proper signed kk-colorations and zero-free proper signed kk-colorations, respectively. Switching isomorphism identifies the six switching-isomorphism classes of sign functions.

Chromatic separation conjecture. (a) Two signed Petersen graphs that are not switching isomorphic have different zero-free chromatic polynomials; in particular, they have different numbers χ(P,σ)∗(4)\chi_{(P,\sigma)}^*(4) of zero-free proper 22-colorations. (b) For any μ≥2\mu\geq 2, the six values χ(P,σ)(2μ+1)\chi_{(P,\sigma)}(2\mu+1) are different for the six switching-isomorphism classes of sign functions, and so are the six values χ(P,σ)∗(2μ)\chi^*_{(P,\sigma)}(2\mu).

The paper proves the analogous separation for ordinary chromatic polynomials and proper 11-colorations, while the zero-free and higher-color claims are proposed as distinguishing properties and remain unproved in the supplied text.

References

Primary source

Thomas Zaslavsky, “Six signed Petersen graphs, and their automorphisms”, arXiv:1303.3347 (2013).

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.