2019/08/01 by Alexandr Kostochka, Kostochka, Alexandr V., Thomas Schweser +3 · 1 citation
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1908.00282
openalex publication_date 2019/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By a graph we mean a finite undirected graph having multiple edges but no loops. Given a graph property P, a P-coloring of a graph G with color set C is a mapping \f:V(G)→ C such that for each color c∈ C the subgraph of G induced by the color class φ-1(c) belongs to P. The P-chromatic number χ(G:P) of G is the least number k for which G admits an P-coloring with a set of k-colors. This coloring concept dates back to the late 1960s and is commonly known as generalized coloring. In the 1980s the P-choice number χ_ℓ(G:P) of G was introduced and investigated by several authors. In 2018 Ďvorák and Postle introduced the DP-chromatic number as a natural extension of the choice number. They also remarked that this concept applies to any graph property. This motivated us to investigate the P-DP-chromatic number χ\rm DP(G:P) of G. We have χ(G:P)≤ χ_ℓ(G:P)≤ χ\rm DP(G:P). In this paper we show that various fundamental coloring results, in particular, the theorems of Brooks, of Gallai, and of Erdős, Rubin and Taylor, have counterparts for the P-DP-chromatic number. Furthermore, we provide a generalization of a result from 2000 about partition of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin, Kostochka, and Toft.