Coloring permutation-gain graphs

  • Daniel Slilaty Department of Mathematics and Statistics Wright State University Dayton, Ohio, USA

Abstract

Correspondence colorings of graphs were introduced in 2018 by Dvořák and Postle as a generalization of list colorings of graphs which generalizes ordinary graph coloring. Kim and Ozeki observed that correspondence colorings generalize various notions of signed-graph colorings which again generalizes ordinary graph colorings. In this note we state how correspondence colorings generalize Zaslavsky's notion of gain-graph colorings and then formulate a new coloring theory of permutation-gain graphs that sits between gain-graph coloring and correspondence colorings. Like Zaslavsky's gain-graph coloring, our new notion of coloring permutation-gain graphs has well defined chromatic polynomials and lifts to colorings of the regular covering graph of a permutation-gain graph.

References

AUTHOR = {Bernshteyn, Anton and Kostochka, Alexandr and Zhu, Xuding},
TITLE = {D{P}-colorings of graphs with high chromatic number},
JOURNAL = {European J. Combin.},
VOLUME = {65},
YEAR = {2017},
PAGES = {122--129},"

AUTHOR = {Dvo\v{r}\'{a}k, Zden\v{e}k and Postle, Luke},
TITLE = {Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8},
JOURNAL = {J. Combin. Theory Ser. B},
VOLUME = {129},
YEAR = {2018},
PAGES = {38--54},}

AUTHOR = {Kang, Yingli and Steffen, Eckhard},
TITLE = {The chromatic spectrum of signed graphs},
JOURNAL = {Discrete Math.},
VOLUME = {339},
YEAR = {2016},
NUMBER = {11},
PAGES = {2660--2663},}

AUTHOR = {Kang, Yingli and Steffen, Eckhard},
TITLE = {Circular coloring of signed graphs},
JOURNAL = {J. Graph Theory},
VOLUME = {87},
YEAR = {2018},
NUMBER = {2},
PAGES = {135--148},}

AUTHOR = {M\'{a}\v{c}ajov\'{a}, Edita and Raspaud, Andr\'{e} and \v{S}koviera, Martin},
TITLE = {The chromatic number of a signed graph},
JOURNAL = {Electron. J. Combin.},
VOLUME = {23},
YEAR = {2016},
NUMBER = {1},
PAGES = {Paper 1.14, 10},}

AUTHOR = {Kim, Seog-Jin and Ozeki, Kenta},
TITLE = {A sufficient condition for {DP}-4-colorability},
JOURNAL = {Discrete Math.},
VOLUME = {341},
YEAR = {2018},
NUMBER = {7},
PAGES = {1983--1986},}

AUTHOR = {Zaslavsky, Thomas},
TITLE = {Signed graph coloring},
JOURNAL = {Discrete Math.},
VOLUME = {39},
YEAR = {1982},
NUMBER = {2},
PAGES = {215--228},}


AUTHOR = {Zaslavsky, Thomas},
TITLE = {Biased graphs. {III}. {C}hromatic and dichromatic invariants},
JOURNAL = {J. Combin. Theory Ser. B},
VOLUME = {64},
YEAR = {1995},
NUMBER = {1},
PAGES = {17--88},}

AUTHOR = {Zaslavsky, Thomas},
TITLE = {Biased graphs. {II}. {T}he three matroids},
JOURNAL = {J. Combin. Theory Ser. B},
FJOURNAL = {Journal of Combinatorial Theory. Series B},
VOLUME = {51},
YEAR = {1991},
NUMBER = {1},
PAGES = {46--72},}
Published
2021-03-19
Section
Articles