2017/09/28 by Seog‐Jin Kim, Kenta Ozeki, Kim, Seog-Jin +1
Computer Science · Engineering · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1709.09807
Dvořák and Postle \citeDP introduced a DP-coloring of a simple graph as a generalization of a list-coloring. They proved a Brooks' type theorem for a DP-coloring, and Bernshteyn, Kostochka and Pron \citeBKP extended it to a DP-coloring of multigraphs. However, detailed structure when a multigraph does not admit a DP-coloring was not specified in \citeBKP. 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.