The Orbital Bivariate Chromatic Polynomial
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909886131994624 |
|---|---|
| author | Dohmen, Klaus Lange-Geisler, Mandy |
| author_facet | Dohmen, Klaus Lange-Geisler, Mandy |
| contents | The orbital bivariate chromatic polynomial, introduced in this article, counts the number of ways to color the vertices of a graph with $λ$ colors such that adjacent vertices either receive distinct colors from a set of $λ$ colors, or the same color from a distinguished subset of $λ-μ$ colors, up to a group of symmetries. This new graph polynomial simultaneously generalizes the orbital chromatic polynomial due to Cameron and Kayibi (2007) and the bivariate chromatic polynomial due to Dohmen, Pönitz, and Tittmann (2003). We discuss fundamental properties, and provide expansions of this new polynomial for various families of graphs, including complete graphs, complete bipartite graphs, paths, and cycles. Some of these expansions are even new for the orbital chromatic polynomial. In addition to these results, we rediscover Fermat's Little Theorem and a ``Fermat-like'' congruence for Lucas numbers. Finally, we outline several open problems related to the orbital bivariate chromatic polynomial. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2009_08235 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The Orbital Bivariate Chromatic Polynomial Dohmen, Klaus Lange-Geisler, Mandy Combinatorics Group Theory Number Theory 05C31 (Primary) 05C15, 05E18, 20B25 (Secondary) The orbital bivariate chromatic polynomial, introduced in this article, counts the number of ways to color the vertices of a graph with $λ$ colors such that adjacent vertices either receive distinct colors from a set of $λ$ colors, or the same color from a distinguished subset of $λ-μ$ colors, up to a group of symmetries. This new graph polynomial simultaneously generalizes the orbital chromatic polynomial due to Cameron and Kayibi (2007) and the bivariate chromatic polynomial due to Dohmen, Pönitz, and Tittmann (2003). We discuss fundamental properties, and provide expansions of this new polynomial for various families of graphs, including complete graphs, complete bipartite graphs, paths, and cycles. Some of these expansions are even new for the orbital chromatic polynomial. In addition to these results, we rediscover Fermat's Little Theorem and a ``Fermat-like'' congruence for Lucas numbers. Finally, we outline several open problems related to the orbital bivariate chromatic polynomial. |
| title | The Orbital Bivariate Chromatic Polynomial |
| topic | Combinatorics Group Theory Number Theory 05C31 (Primary) 05C15, 05E18, 20B25 (Secondary) |
| url | https://arxiv.org/abs/2009.08235 |