Defective DP-colorings of sparse multigraphs

DOI10.1016/j.ejc.2020.103267zbMath1458.05071arXiv1912.03421OpenAlexW3113087259MaRDI QIDQ2225451

Fuhong Ma, Pongpat Sittitrai, Yifan Jing, Jingwei Xu, Alexandr V. Kostochka

Publication date: 8 February 2021

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items

Decomposing planar graphs into graphs with degree restrictions, 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, Defective DP-colorings of sparse simple graphs, Relaxed DP-3-coloring of planar graphs without some cycles

Cites Work

• Unnamed Item
• Unnamed Item
• On 1-improper 2-coloring of sparse graphs
• 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
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Planar graphs are 1-relaxed, 4-choosable
• Defective and clustered graph colouring
• List improper colorings of planar graphs with prescribed girth
• 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
• On DP-coloring of graphs and multigraphs
• Defective 2-colorings of sparse graphs
• Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions
• Limits of Near-Coloring of Sparse Graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Defective choosability of graphs in surfaces
• A Relative of Hadwiger's Conjecture
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• A note on defective colorings of graphs in surfaces
• List Improper Colourings of Planar Graphs
• Improper colourings inspired by Hadwiger's conjecture
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Defective and clustered choosability of sparse graphs
• Improper choosability of graphs and maximum average degree