DP-degree colorable hypergraphs

DOI10.1016/J.TCS.2019.09.010MaRDI QIDQ2333798zbMATH OpenOpenAlexFDO

Authors Thomas Schweser

Publication date 13 November 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Brooks' theoremcorrespondence coloringDP-coloringhypergraph coloringlist-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

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.

Review text

\textit{Z. Dvořák} and \textit{L. Postle} [J. Comb. Theory, Ser. B 129, 38--54 (2018; Zbl 1379.05034)] introduced under the name correspondence coloring a coloring concept to study list coloring problems of graphs. Later, \textit{A. Yu. Bernshteyn} et al. [Sib. Math. J. 58, No. 1, 28--36 (2017; Zbl 1366.05038); translation from Sib. Mat. Zh. 58, No. 1, 36--47 (2017)] introduced the now established name DP-coloring for this concept. DP-coloring turned out to be a very useful method to study graph coloring problems. This paper generalizes the concept of DP-coloring to hypergraphs, and it proves a Brooks-type result for the DP-chromatic number of a hypergraph by characterizing the DP-degree colorable hypergraphs, and the corresponding ``bad covers.

Recommendations

• DP-colorings of hypergraphs
• A note on a Brooks' type theorem for DP-coloring
• On DP‐coloring of digraphs
• On DP-coloring of graphs and multigraphs
• DP-colorings of graphs with high chromatic number

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)