1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Burnside Chromatic Polynomials of Group-Invariant Graphs

Published Online: 21 Jan 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 02 Mar 2018
Accepted: 17 Jul 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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 𝕲 acting on a graph G and a 𝕲-set X, a proper X-coloring is a function with no monochromatic edge orbit. The set of proper colorings is a 𝕲-set which induces a polynomial function from the Burnside ring of 𝕲 to itself. In this paper, we study many properties of the Burnside chromatic polynomial, answering some questions of Zaslavsky.

Keywords

MSC 2010

[1] N. Biggs, Algebraic Graph Theory (Cambridge Tracts in Mathematics, Cambridge University Press, London, 1974). doi:10.1017/CBO978051160870410.1017/CBO9780511608704Search in Google Scholar

[2] G.S. Bowlin, Maximum frustration in bipartite signed graphs, Electron. J. Combin. 19 (2012) #P10. doi:10.37236/220410.37236/2204Search in Google Scholar

[3] J.L. Gross, Voltage graphs, Discrete Math. 9 (1974) 239–246. doi:10.1016/0012-365X(74)90006-510.1016/0012-365X(74)90006-5Search in Google Scholar

[4] J.L. Gross and T.W. Tucker, Topological Graph Theory (John Wiley & Sons, Inc., New York, 1987).Search in Google Scholar

[5] F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953) 143–146. doi:10.1307/mmj/102898991710.1307/mmj/1028989917Search in Google Scholar

[6] G.-C. Rota, On the foundations of combinatorial theory: I. Theory of Möbius functions, Z. Wahrscheinlichkeitsteorie verw Gebiete 2 (1964) 340–368. doi:10.1007/BF0053193210.1007/BF00531932Search in Google Scholar

[7] L. Solomon, The Burnside algebra of a finite group, J. Combin. Theory 2 (1967) 603–615. doi:10.1016/S0021-9800(67)80064-410.1016/S0021-9800(67)80064-4Search in Google Scholar

[8] R.P. Stanley, Enumerative Combinatorics, Vol. 1, in: Wadsworth & Brooks/Cole, Math. Ser. (Springer, Boston, 1986). doi:10.1007/978-1-4615-9763-610.1007/978-1-4615-9763-6Search in Google Scholar

[9] R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171–178. doi:10.1016/0012-365X(73)90108-810.1016/0012-365X(73)90108-8Search in Google Scholar

[10] H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932) 572–579. doi:10.1090/S0002-9904-1932-05460-X10.1090/S0002-9904-1932-05460-XSearch in Google Scholar

[11] T. Zaslavsky, Totally frustrated states in the chromatic theory of gain graphs, European J. Combin. 30 (2009) 133–156. doi:10.1016/j.ejc.2008.02.00410.1016/j.ejc.2008.02.004Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo