Limits of Near-Coloring of Sparse Graphs

DOI10.1002/jgt.21731zbMath1280.05040OpenAlexW1897251248MaRDI QIDQ2874099

Mickaël Montassier, Tomáš Kaiser, Paul Dorbec, Andre Raspaud

Publication date: 28 January 2014

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.21731

zbMATH Keywords

coloringsmaximum average degreeimproper colorings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (9)

Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Defective DP-colorings of sparse simple graphs ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Maximum average degree and relaxed coloring ⋮ Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions ⋮ Relaxed equitable colorings of planar graphs with girth at least 8 ⋮ Defective and clustered choosability of sparse graphs

Cites Work

• Unnamed Item
• \((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
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• List improper colorings of planar graphs with prescribed girth
• Path partitions of planar graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• List Improper Colourings of Planar Graphs
• Improper choosability of graphs and maximum average degree

This page was built for publication: Limits of Near-Coloring of Sparse Graphs