Premium
A note on a Brooks' type theorem for DP‐coloring
Author(s) -
Kim SeogJin,
Ozeki Kenta
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22425
Subject(s) - mathematics , list coloring , combinatorics , edge coloring , generalization , greedy coloring , complete coloring , fractional coloring , brooks' theorem , multigraph , type (biology) , simple (philosophy) , discrete mathematics , graph , chordal graph , 1 planar graph , mathematical analysis , ecology , philosophy , epistemology , line graph , graph power , biology
Dvořák and Postle introduced DP‐coloring of simple graphs as a generalization of list‐coloring. They proved a Brooks' type theorem for DP‐coloring; and Bernshteyn, Kostochka, and Pron extended it to DP‐coloring of multigraphs. However, detailed structure, when a multigraph does not admit DP‐coloring, was not specified. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.