Irreducibility of interlace polynomials
The factorisation of graph polynomials often reflects combinatorial decomposition. For a nonempty loopless graph $G$, we first prove that the two-variable interlace polynomial $q(G;x,y)$, introduced by Arratia, Bollobás and Sorkin, is irreducible over $\mathbb{C}[x,y]$ if and only if $G$ is connected, exactly paralleling the classical irreducibility theorem for the Tutte polynomial. The loopless hypothesis is essential: we construct an infinite family of connected looped graphs whose two-variable interlace polynomials are reducible. For a nonempty graph $G$, we prove that Courcelle's…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.07847
curl -X POST /api/v1/records/arxiv/2608.07847/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.07847/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'