Generalized DP-colorings of graphs

DOI10.1016/J.DISC.2022.113186MaRDI QIDQ6091813zbMATH OpenOpenAlexFDO

Authors Alexandr Kostochka, Thomas Schweser, Michael Stiebitz

Publication date 27 November 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.00282

zbMATH Keywords

Brooks' theoremdegeneracyDP-coloringgeneralized coloring of graphslist-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: By a graph we mean a finite undirected graph having multiple edges but no loops. Given a graph property $mathcalP$, a $mathcalP$-coloring of a graph $G$ with color set $C$ is a mapping $f:V(G)oC$ such that for each color $cinC$ the subgraph of $G$ induced by the color class $varph{i}^{-1}(c)$ belongs to $mathcalP$. The $mathcalP$-chromatic number $chi(G:mathcalP)$ of $G$ is the least number $k$ for which $G$ admits an $mathcalP$-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 $mathcalP$-choice number $ch{i}_{e}ll(G:mathcalP)$ of $G$ was introduced and investigated by several authors. In 2018 v{D}vor'ak 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 $mathcalP$-DP-chromatic number $ch{i}_{mDP}(G:mathcalP)$ of $G$. We have $chi(G:mathcalP)leqch{i}_{e}ll(G:mathcalP)leqch{i}_{mDP}(G:mathcalP)$. In this paper we show that various fundamental coloring results, in particular, the theorems of Brooks, of Gallai, and of ErdH{o}s, Rubin and Taylor, have counterparts for the $mathcalP$-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.

Review text

In this paper, the authors present generalizations of various classical coloring results. For this, the authors extend three coloring concepts for the class of finite graphs (with multiple edges allowed and no loops). They are the generalized coloring concept, in which the same colored vertices of a graph induce a subgraph satisfying a prescribed graph property; the concept of variable degeneracy [\textit{O. V. Borodin} et al., ibid. 214, No. 1--3, 101--112 (2000; Zbl 0949.05029)], which makes it possible to give a common generalization of the point partition number and the list chromatic number; and the \(DP\)-coloring concept [\textit{Z. Dvořák} and \textit{L. Postle}, J. Comb. Theory, Ser. B 129, 38--54 (2018; Zbl 1379.05034)], where a list assignment of a graph is replaced by a cover. Combining these three coloring concepts the authors present generalizations of various classical coloring results, such as the theorems of \textit{R. L. Brooks} [Proc. Camb. Philos. Soc. 37, 194--197 (1941; Zbl 0027.26403)], of \textit{T. Gallai} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165--192 (1963; Zbl 0121.18401)], and of \textit{P. Erdős} et al. [in: Proceedings of the West Coast Conference on combinatorics, graph theory and computing, Humboldt State University, Arcata, California, September 5--7, 1979. Winnipeg, MB: Utilitas Mathematica Publishing Inc. 125--157 (1980; Zbl 0469.05032)]. Their main result is a \(DP\)-version of a theorem about partitions of graphs into a fixed number of induced subgraphs with bounded variable degeneracy due to Borodin et al. [loc. cit.].

Recommendations

• A generalization of some results on list coloring and DP-coloring
• DP-degree colorable hypergraphs
• DP-colorings of graphs with high chromatic number
• A note on a Brooks' type theorem for DP-coloring

Cites work

• k-Degenerate Graphs
• A list version of Dirac's theorem on the number of edges in colour-critical graphs
• A new lower bound on the number of edges in colour-critical graphs and hypergraphs
• A note on a Brooks' type theorem for DP-coloring
• A survey of hereditary properties of graphs
• A Theorem of R. L. Brooks and a Conjecture of H. Hadwiger
• An analogue of DP-coloring for variable degeneracy and its applications
• An extension of Brooks' theorem to n-degenerate graphs
• Color-critical graphs on a fixed surface
• Colour-critical graphs with few edges
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Critical Point-Arboritic Graphs
• Destroying noncomplete regular components in graph partitions
• DP-degree colorable hypergraphs
• Gallai's innequality for critical graphs of reducible hereditary properties
• Generalized hypergraph coloring
• Generalized list colourings of graphs
• scientific article; zbMATH DE number 3661375 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Improved lower bounds on the number of edges in list critical and online list critical graphs
• On DP-coloring of graphs and multigraphs
• On list critical graphs
• On Partitioning Planar Graphs
• On the critical point-arboricity graphs
• Optimal Vertex Partitions
• Ore's conjecture on color-critical graphs is almost true
• Partitioning and coloring graphs with degree constraints
• Partitions of hypergraphs under variable degeneracy constraints
• Sharp Dirac's theorem for DP-critical graphs
• The number of edges in critical graphs.
• The structure of k-chromatic graphs
• The subchromatic number of a graph
• Two results on the digraph chromatic number
• Variable degeneracy: Extensions of Brooks' and Gallai's theorems

Cited in

(7)

• Variable degeneracy: Extensions of Brooks' and Gallai's theorems
• An analogue of DP-coloring for variable degeneracy and its applications
• DP-colorings of hypergraphs
• Partial DP-coloring of graphs
• On DP‐coloring of digraphs
• Variable degeneracy on toroidal graphs
• Brooks-type colourings of digraphs in linear time

This page was built for publication: Generalized DP-colorings of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6091813)