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