DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

J.A. White

Jacob White

School of Mathematical and Statistical Sciences
University of Texas - Rio Grande Valley
Edinburg, TX, USA 78539

email: jacob.white@utrgv.edu

Title:

Burnside chromatic polynomials of group-invariant graphs

PDF

Source:

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:

  1. N. Biggs, Algebraic Graph Theory (Cambridge Tracts in Mathematics, Cambridge University Press, London, 1974).
    https://doi.org/10.1017/CBO9780511608704
  2. G.S. Bowlin, Maximum frustration in bipartite signed graphs, Electron. J. Combin. 19 (2012) #P10.
    https://doi.org/10.37236/2204
  3. J.L. Gross, Voltage graphs, Discrete Math. 9 (1974) 239–246.
    https://doi.org/10.1016/0012-365X(74)90006-5
  4. J.L. Gross and T.W. Tucker, Topological Graph Theory (John Wiley & Sons, Inc., New York, 1987).
  5. 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
  6. 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
  7. 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
  8. 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
  9. R.P. Stanley, Acyclic orientations of graphs, Discrete Math. 5 (1973) 171–178.
    https://doi.org/10.1016/0012-365X(73)90108-8
  10. 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
  11. 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