Chromatic polynomials of signed graphs and dominating-vertex deletion formulae
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _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 |