Sparse critical graphs for defective DP-colorings

DOI10.1016/J.DISC.2024.113899MaRDI QIDQ6204323zbMATH OpenOpenAlexWikidataFDO

Authors Alexandr Kostochka, Jingwei Xu

Publication date 27 March 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

defective coloringDP-coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: An interesting generalization of list coloring is so called DP-coloring (named after Dvov{r}'ak and Postle). We study $(i,j)$-defective DP-colorings of simple graphs. Define $g_{DP}(i,j,n)$ to be the minimum number of edges in an $n$-vertex DP-$(i,j)$-critical graph. We prove sharp bounds on $g_{DP}(i,j,n)$ for $i=1,2$ and $jgeq2i$ for infinitely many $n$.

Recommendations

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

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
• Defective DP-colorings of sparse simple graphs
• 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
• 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

(1)

• Sparse critical graphs for defective (1, 3)-coloring

This page was built for publication: Sparse critical graphs for defective DP-colorings

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