Defective DP-colorings of sparse simple graphs

DOI10.1016/J.DISC.2021.112637MaRDI QIDQ2237221zbMATH OpenOpenAlexFDO

Authors Yifan Jing, Fuhong Ma, Jingwei Xu, Alexandr Kostochka

Publication date 27 October 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

defective coloringDP-coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvov{r}'ak and Postle. We introduce and study $(i,j)$-defective DP-colorings of simple graphs. Let $g_{DP}(i,j,n)$ be the minimum number of edges in an $n$-vertex DP-$(i,j)$-critical graph. In this paper we determine sharp bound on $g_{DP}(i,j,n)$ for each $igeq3$ and $jgeq2i+1$ for infinitely many $n$.

Recommendations

• Defective DP-colorings of sparse multigraphs
• On 2-defective DP-colorings of sparse graphs
• Fractional DP-colorings of sparse graphs
• Sharp Dirac's theorem for DP-critical graphs
• DP-colorings of graphs with high chromatic number

Cites work

• \((k,1)\)-coloring of sparse graphs
• \((k,j)\)-coloring of sparse graphs
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• A note on defective colorings of graphs in surfaces
• A relative of Hadwiger's conjecture
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Defective 2-colorings of sparse graphs
• Defective and clustered choosability of sparse graphs
• Defective and clustered graph colouring
• Defective choosability of graphs in surfaces
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Defective colouring of graphs excluding a subgraph or minor
• Defective DP-colorings of sparse multigraphs
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• Improper choosability of graphs and maximum average degree
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Improper coloring of sparse graphs with a given girth. II: Constructions
• Improper colourings inspired by Hadwiger's conjecture
• Limits of near-coloring of sparse graphs
• List improper colorings of planar graphs with prescribed girth
• List Improper Colourings of Planar Graphs
• Maximum average degree and relaxed coloring
• On 1-improper 2-coloring of sparse graphs
• On 2-defective DP-colorings of sparse graphs
• On DP-coloring of graphs and multigraphs
• Planar graphs are 1-relaxed, 4-choosable
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

Cited in

(11)

• Relaxed DP-3-coloring of planar graphs without some cycles
• On 2-defective DP-colorings of sparse graphs
• Defective DP-colorings of sparse multigraphs
• Sharp Dirac's theorem for DP-critical graphs
• Fractional DP-colorings of sparse graphs
• The Johansson-Molloy theorem for DP-coloring
• DP‐coloring Cartesian products of graphs
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• A weak DP-coloring of planar graphs without 4- and 9-cycles
• Sparse critical graphs for defective DP-colorings
• Sparse critical graphs for defective (1, 3)-coloring

This page was built for publication: Defective DP-colorings of sparse simple graphs

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