A note on a Brooks' type theorem for DP‐coloring. Issue 2 (28th November 2018)

• Record Type: Journal Article
• Authors: Kim, Seog‐Jin; Ozeki, Kenta
• Is Part Of: Journal of graph theory. Volume 91:Issue 2(2019)
• Page Start: 148
• Page End: 161
• Publication Date: 2018-11-28
• Subjects: Brooks' type theorem -- coloring -- DP‐coloring -- list‐coloring; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22425
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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.