Counting subgraphs of coloring graphs
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_ | 1866915271665516544 |
|---|---|
| author | Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. Russell, Heather M. |
| author_facet | Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. Russell, Heather M. |
| contents | The chromatic polynomial $π_{G}(k)$ of a graph $G$ can be viewed as counting the number of vertices in a family of coloring graphs $\mathcal C_k(G)$ associated with (proper) $k$-colorings of $G$ as a function of the number of colors $k$. These coloring graphs can be understood as a reconfiguration system. We generalize the chromatic polynomial to $π_G^{(H)}(k)$, counting occurrences of arbitrary induced subgraphs $H$ in these coloring graphs, and we prove that these functions are polynomial in $k$. In particular, we study the chromatic pairs polynomial $π_{G}^{(P_2)}(k)$, which counts the number of edges in coloring graphs, corresponding to the number of pairs of colorings that differ on a single vertex. We show two trees share a chromatic pairs polynomial if and only if they have the same degree sequence, and we conjecture that the chromatic pairs polynomial refines the chromatic polynomial in general. We also instantiate our polynomials with other choices of $H$ to generate new graph invariants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_12883 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Counting subgraphs of coloring graphs Asgarli, Shamil Krehbiel, Sara Levinson, Howard W. Russell, Heather M. Combinatorics 05C15, 05C31 The chromatic polynomial $π_{G}(k)$ of a graph $G$ can be viewed as counting the number of vertices in a family of coloring graphs $\mathcal C_k(G)$ associated with (proper) $k$-colorings of $G$ as a function of the number of colors $k$. These coloring graphs can be understood as a reconfiguration system. We generalize the chromatic polynomial to $π_G^{(H)}(k)$, counting occurrences of arbitrary induced subgraphs $H$ in these coloring graphs, and we prove that these functions are polynomial in $k$. In particular, we study the chromatic pairs polynomial $π_{G}^{(P_2)}(k)$, which counts the number of edges in coloring graphs, corresponding to the number of pairs of colorings that differ on a single vertex. We show two trees share a chromatic pairs polynomial if and only if they have the same degree sequence, and we conjecture that the chromatic pairs polynomial refines the chromatic polynomial in general. We also instantiate our polynomials with other choices of $H$ to generate new graph invariants. |
| title | Counting subgraphs of coloring graphs |
| topic | Combinatorics 05C15, 05C31 |
| url | https://arxiv.org/abs/2401.12883 |