Abstract:The orbital bivariate chromatic polynomial, introduced in this article, counts the number of ways to color the vertices of a graph with $\lambda$ colors such that adjacent vertices either receive distinct colors from a set of $\lambda$ colors, or the same color from a distinguished subset of $\lambda-\mu$ 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, cycles, and wheels. Some of these expansions are even new for the orbital chromatic polynomial. As a side result, we obtain a ``Fermat-like'' congruence for Lucas sequences, which generalizes Fermat's Little Theorem. Finally, we outline open problems related to the orbital bivariate chromatic polynomial.
From: Klaus Dohmen [view email]
[v1]
Thu, 17 Sep 2020 12:39:17 UTC (7 KB)
[v2]
Fri, 15 Aug 2025 18:27:44 UTC (8 KB)
[v3]
Fri, 19 Sep 2025 23:08:52 UTC (16 KB)
[v4]
Tue, 4 Nov 2025 11:34:11 UTC (21 KB)
[v5]
Mon, 3 Aug 2026 12:33:27 UTC (19 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。