Maximum average degree and relaxed coloring

DOI10.1016/j.disc.2017.06.014zbMath1367.05075arXiv1806.07021OpenAlexW2730472093MaRDI QIDQ2012543

Gexin Yu, Michael Kopreski

Publication date: 1 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

maximum average degreerelaxed coloringglobal discharging

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (6)

Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ Sparse critical graphs for defective DP-colorings ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Defective DP-colorings of sparse simple graphs ⋮ Defective and clustered choosability of sparse graphs

Cites Work

• On 1-improper 2-coloring of sparse graphs
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• Limits of Near-Coloring of Sparse Graphs
• Improper choosability of graphs and maximum average degree

This page was built for publication: Maximum average degree and relaxed coloring