Article in volume
Authors:
Title:
Burnside chromatic polynomials of group-invariant graphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 55-76
Received: 2018-03-02 , Revised: 2020-06-15 , Accepted: 2020-07-17 , Available online: 2020-12-28 , https://doi.org/10.7151/dmgt.2385
Abstract:
We introduce the Burnside chromatic polynomial of a graph that is invariant
under a group action. This is a generalization of the $Q$-chromatic function
Zaslavsky introduced for gain graphs. Given a group $\mathfrak{G}$ acting on a graph
$G$ and a $\mathfrak{G}$-set $X$, a proper $X$-coloring is a function with no
monochromatic edge orbit. The set of proper colorings is a $\mathfrak{G}$-set which
induces a polynomial function from the Burnside ring of $\mathfrak{G}$ to itself.
In this paper, we study many properties of the Burnside chromatic polynomial,
answering some questions of Zaslavsky.
Keywords:
chromatic polynomial, Burnside ring, gain graph, polynomial function
References:
- N. Biggs, Algebraic Graph Theory (Cambridge Tracts in Mathematics, Cambridge University Press, London, 1974).
https://doi.org/10.1017/CBO9780511608704 - G.S. Bowlin, Maximum frustration in bipartite signed graphs, Electron. J. Combin. 19 (2012) #P10.
https://doi.org/10.37236/2204 - J.L. Gross, Voltage graphs, Discrete Math. 9 (1974) 239–246.
https://doi.org/10.1016/0012-365X(74)90006-5 - J.L. Gross and T.W. Tucker, Topological Graph Theory (John Wiley & Sons, Inc., New York, 1987).
- F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953) 143–146.
https://doi.org/10.1307/mmj/1028989917 - G.-C. Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions, Z. Wahrscheinlichkeitsteorie verw Gebiete 2 (1964) 340–368.
https://doi.org/10.1007/BF00531932 - L. Solomon, The Burnside algebra of a finite group, J. Combin. Theory 2 (1967) 603–615.
https://doi.org/10.1016/S0021-9800(67)80064-4 - R.P. Stanley, Enumerative Combinatorics, Vol. 1, in: Wadsworth & Brooks/Cole, Math. Ser. (Springer, Boston, 1986).
https://doi.org/10.1007/978-1-4615-9763-6 - R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171–178.
https://doi.org/10.1016/0012-365X(73)90108-8 - H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572–579.
https://doi.org/10.1090/S0002-9904-1932-05460-X - T. Zaslavsky, Totally frustrated states in the chromatic theory of gain graphs, European J. Combin. 30 (2009) 133–156.
https://doi.org/10.1016/j.ejc.2008.02.004
Close