On DP-coloring of graphs and multigraphs

DOI10.1134/S0037446617010049MaRDI QIDQ2360256zbMATH OpenFDO

Authors Anton Bernshteyn, S. P. Pron, Alexandr Kostochka

Publication date 30 June 2017

Published in Siberian Mathematical Journal (Search for Journal in Brave)

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

zbMATH Keywords

critical graphslist coloringvertex degrees

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: While solving a question on list coloring of planar graphs, Dvov{r}'{a}k and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph $G$ reduces the problem of finding a coloring of $G$ from a given list $L$ to the problem of finding a "large" independent set in an auxiliary graph $H(G,L)$ with vertex set $(v,c),:,vinV(G)extandcinL(v)$. It is similar to the old reduction by Plesneviv{c} and Vizing of the $k$-coloring problem to the problem of finding an independent set of size $|V(G)|$ in the Cartesian product $Gsquare{K}_k$. Some properties of the DP-chromatic number $ch{i}_{DP}(G)$ resemble the properties of the list chromatic number $ch{i}_{ell}(G)$ but some differ quite a lot. It is always the case that $ch{i}_{DP}(G)geqch{i}_{ell}(G)$. The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and ErdH{o}s, Rubin, and Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai's Theorem on the minimum number of edges in $n$-vertex graphs critical with respect to DP-coloring.

Recommendations

• Defective DP-colorings of sparse multigraphs
• DP-colorings of graphs with high chromatic number
• DP-degree colorable hypergraphs
• A note on a Brooks' type theorem for DP-coloring
• Sharp Dirac's theorem for DP-critical graphs

Cites work

• Colorings and orientations of graphs
• Colorings of plane graphs: a survey
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• 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 1496580 (Why is no real title available?)
• scientific article; zbMATH DE number 3230034 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• scientific article; zbMATH DE number 3195967 (Why is no real title available?)
• The asymptotic behavior of the correspondence chromatic number
• The colour theorems of Brooks and Gallai extended

Cited in

(63)

• DP-3-coloring of some planar graphs
• A sufficient condition for DP-4-colorability
• A note on the DP-chromatic number of complete bipartite graphs
• Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Sufficient conditions on planar graphs to have a relaxed DP-3-coloring
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Answers to two questions on the DP color function
• Differences between the list-coloring and DP-coloring for planar graphs
• Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions
• An analogue of DP-coloring for variable degeneracy and its applications
• Cover and variable degeneracy
• DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles
• Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles
• An extension of Thomassen's result on choosability
• Upper bound for DP-chromatic number of a graph
• A deletion-contraction relation for the DP color function
• A generalization of some results on list coloring and DP-coloring
• On-line DP-coloring of graphs
• On the chromatic polynomial and counting DP-colorings of graphs
• On 2-defective DP-colorings of sparse graphs
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs
• DP-4-colorability of planar graphs without adjacent cycles of given length
• Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable
• DP-degree colorable hypergraphs
• DP-colorings of graphs with high chromatic number
• DP-colorings of hypergraphs
• On digraph coloring problems and treewidth duality
• Partial DP-coloring of graphs
• Planar graphs without \(\{4, 6, 8\}\)-cycles are 3-choosable
• Notes on the harmonic index of graphs
• On the f-coloring of multigraphs
• Sharp Dirac's theorem for DP-critical graphs
• On DP‐coloring of digraphs
• Fractional DP-colorings of sparse graphs
• A note on a Brooks' type theorem for DP-coloring
• Weak degeneracy of graphs
• Every planar graph without 5-cycles adjacent to 6-cycles is DP-4-colorable
• DP‐coloring Cartesian products of graphs
• Generalized DP-colorings of graphs
• Symmetric set coloring of signed graphs
• The relation between the harmonic index and some coloring parameters
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• Decomposition of toroidal graphs without some subgraphs
• A weak DP-coloring of planar graphs without 4- and 9-cycles
• An algebraic approach for counting DP-3-colorings of sparse graphs
• Sparse critical graphs for defective DP-colorings
• A note on fractional DP-coloring of graphs
• Sufficient conditions make graphs edge DP--colorable
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• On DP-coloring of outerplanar graphs
• Degree-truncated DP-colourability of \(K_{2, 4}\)-minor-free graphs
• Degree-truncated choosability of graphs
• DP-coloring of graphs from random covers
• Group connectivity in 3-edge-connected signed graphs
• Some orientation theorems for restricted DP-colorings of graphs
• A lower bound on the number of edges in DP-critical graphs
• On strongly and robustly critical graphs
• Tight minimum degree conditions for apex-outerplanar minors and subdivisions in graphs and digraphs
• Planar graphs without \(5^-\)-cycles at distance less than 3 are \((\mathcal{I}, \mathcal{F})\)-colorable
• Arc-weighted acyclic orientation of graphs
• The harmonic index of a graph and its DP-chromatic number

This page was built for publication: On DP-coloring of graphs and multigraphs

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