Chromatic polynomials of signed graphs and dominating-vertex deletion formulae
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914852999528448 |
|---|---|
| author | Greaves, Gary R. W. Syatriadi, Jeven Utomo, Charissa I. |
| author_facet | Greaves, Gary R. W. Syatriadi, Jeven Utomo, Charissa I. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_00883 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Chromatic polynomials of signed graphs and dominating-vertex deletion formulae Greaves, Gary R. W. Syatriadi, Jeven Utomo, Charissa I. Combinatorics 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. |
| title | Chromatic polynomials of signed graphs and dominating-vertex deletion formulae |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.00883 |