Defective DP-colorings of sparse multigraphs

DOI10.1016/J.EJC.2020.103267zbMATH Open1458.05071arXiv1912.03421OpenAlexW3113087259MaRDI QIDQ2225451FDOQ2225451

Authors: Yifan Jing, Fuhong Ma, Pongpat Sittitrai, Jingwei Xu, Alexandr Kostochka 

Publication date: 8 February 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvorak and Postle. We introduce and study $(i,j)$-defective DP-colorings of multigraphs. We concentrate on sparse multigraphs and consider $f_{DP}(i,j,n)$ --- the minimum number of edges that may have an $n$-vertex $(i,j)$-critical multigraph, that is, a multigraph $G$ that has no $(i,j)$-defective DP-coloring but whose every proper subgraph has such a coloring. For every $i$ and $j$, we find linear lower bounds on $f_{DP}(i,j,n)$ that are exact for infinitely many $n$.

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

Recommendations

• Defective DP-colorings of sparse simple graphs
• On 2-defective DP-colorings of sparse graphs
• On DP-coloring of graphs and multigraphs
• Fractional DP-colorings of sparse graphs
• DP-colorings of graphs with high chromatic number

zbMATH Keywords

correspondence coloring\(n\)-vertex \((i,j)\)-critical multigraph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Sharp Dirac's theorem for DP-critical graphs
• A weak DP-partitioning of planar graphs without 4-cycles and 6-cycles
• On 2-defective DP-colorings of sparse graphs
• Decomposing planar graphs into graphs with degree restrictions
• On DP-coloring of graphs and multigraphs
• A weak DP-coloring of planar graphs without 4- and 9-cycles
• Sparse critical graphs for defective DP-colorings
• Fractional DP-colorings of sparse graphs
• Relaxed DP-3-coloring of planar graphs without some cycles
• Defective DP-colorings of sparse simple graphs

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

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