Abstract: In order to solve a question on list coloring of planar graphs, Dvov{r}'{a}k and Postle introduced the concept of so called DP-coloring, thereby extending the concept of list-coloring. DP-coloring was anaylized in detail by Bernshteyn, Kostochka, and Pron for graphs and multigraphs; they characterized DP-degree colorable multigraphs and deduced a Brooks' type result from this. The characterization of the corresponding 'bad' covers was later given by Kim and Ozeki. In this paper, the concept of DP-colorings is extended to hypergraphs having multiple (hyper-)edges. We characterize the DP-degree colorable hypergraphs and, furthermore, the corresponding 'bad' covers. This gives a Brooks' type result for the DP-chromatic number of a hypergraph. In the last part, we examine DP-critical graphs and establish some basic facts on their structure as well as a Gallai-type bound on the minimum number of edges.
Recommendations
Cites work
- A note on a Brooks' type theorem for DP-coloring
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
- DP-colorings of graphs with high chromatic number
- DP-colorings of hypergraphs
- scientific article; zbMATH DE number 3735847 (Why is no real title available?)
- scientific article; zbMATH DE number 3503283 (Why is no real title available?)
- scientific article; zbMATH DE number 3537704 (Why is no real title available?)
- scientific article; zbMATH DE number 3563170 (Why is no real title available?)
- scientific article; zbMATH DE number 3230034 (Why is no real title available?)
- scientific article; zbMATH DE number 3043302 (Why is no real title available?)
- On chromatic number of graphs and set-systems
- On DP-coloring of graphs and multigraphs
- Sharp Dirac's theorem for DP-critical graphs
- The colour theorems of Brooks and Gallai extended
Cited in
(10)- Combinatorial Nullstellensatz and DP-coloring of graphs
- Cover and variable degeneracy
- DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces
- On DP-coloring of graphs and multigraphs
- DP-colorings of hypergraphs
- Partial DP-coloring of graphs
- On DP‐coloring of digraphs
- A note on a Brooks' type theorem for DP-coloring
- Generalized DP-colorings of graphs
- Variable degeneracy on toroidal graphs
This page was built for publication: DP-degree colorable hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2333798)
