On DP-coloring of graphs and multigraphs

DOI10.1134/S0037446617010049zbMath1366.05038arXiv1609.00763MaRDI QIDQ2360256

Anton Bernshteyn, S. P. Pron, Alexandr V. 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

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

Related Items (41)

DP-3-coloring of some planar graphs ⋮ 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 ⋮ DP-colorings of graphs with high chromatic number ⋮ Partial DP-coloring of graphs ⋮ Planar graphs without \(\{4, 6, 8\}\)-cycles are 3-choosable ⋮ Weak degeneracy of graphs ⋮ Notes on the harmonic index of graphs ⋮ A generalization of some results on list coloring and DP-coloring ⋮ Generalized DP-colorings of graphs ⋮ Symmetric set coloring of signed graphs ⋮ The relation between the harmonic index and some coloring parameters ⋮ On-line DP-coloring of graphs ⋮ 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 ⋮ Unnamed Item ⋮ 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 ⋮ Every planar graph without pairwise adjacent 3-, 4-, and 5-cycle is DP-4-colorable ⋮ Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8 ⋮ A sufficient condition for DP-4-colorability ⋮ 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 ⋮ A note on the DP-chromatic number of complete bipartite graphs ⋮ Differences between the list-coloring and DP-coloring for planar graphs ⋮ Group colorings and DP-colorings of multigraphs using edge-disjoint decompositions ⋮ DP-4-colorability of planar graphs without adjacent cycles of given length ⋮ An analogue of DP-coloring for variable degeneracy and its applications ⋮ Planar graphs without cycles of lengths 4 and 5 and close triangles are DP-3-colorable ⋮ Cover and variable degeneracy ⋮ DP-\(4\)-colorability of planar graphs without intersecting \(5\)-cycles ⋮ The harmonic index of a graph and its DP-chromatic number ⋮ DP-degree colorable hypergraphs ⋮ Relaxed DP-coloring and another generalization of DP-coloring on planar graphs without 4-cycles and 7-cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Colorings and orientations of graphs
• The colour theorems of Brooks and Gallai extended
• Colorings of plane graphs: a survey
• The asymptotic behavior of the correspondence chromatic number

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