Open Access. Powered by Scholars. Published by Universities.®

Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Applied Statistics

Mathematics and Statistics Faculty Publications

2021

Correspondence colorings of graphs

Articles 1 - 1 of 1

Full-Text Articles in Mathematics

Coloring Permutation-Gain Graphs, Daniel Slilaty Jan 2021

Coloring Permutation-Gain Graphs, Daniel Slilaty

Mathematics and Statistics Faculty Publications

Correspondence colorings of graphs were introduced in 2018by Dvoˇr ́ak and Postle as a generalization of list colorings of graphswhich generalizes ordinary graph coloring. Kim and Ozeki observed thatcorrespondence colorings generalize various notions of signed-graph col-orings which again generalizes ordinary graph colorings. In this notewe state how correspondence colorings generalize Zaslavsky’s notionof gain-graph colorings and then formulate a new coloring theory ofpermutation-gain graphs that sits between gain-graph coloring and cor-respondence colorings. Like Zaslavsky’s gain-graph coloring, our newnotion of coloring permutation-gain graphs has well defined chromaticpolynomials and lifts to colorings of the regular covering graph of apermutation-gain graph