2024/07/01 by Gary R. W. Greaves, Greaves, Gary R. W., Jeven Syatriadi +3
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Advanced Combinatorial Mathematics
paper · pdf · doi:10.48550/arxiv.2407.00883
We exhibit non-switching-isomorphic signed graphs that share a common underlying graph and common chromatic polynomials, thereby answering a question posed by Zaslavsky. For various joins of all-positive or all-negative signed complete graphs, we derive a closed-form expression for their chromatic polynomials. As a generalisation of the chromatic polynomials for a signed graph, we introduce a new pair of bivariate chromatic polynomials. We establish recursive dominating-vertex deletion formulae for these bivariate chromatic polynomials. Finally, we show that for certain families of signed threshold graphs, isomorphism is equivalent to the equality of bivariate chromatic polynomials.