Limits of near-coloring of sparse graphs

DOI10.1002/JGT.21731MaRDI QIDQ2874099zbMATH OpenOpenAlexFDO

Authors Paul Dorbec, Tomáš Kaiser, Mickaël Montassier, André 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

coloringsimproper coloringsmaximum average degree

Mathematics Subject Classification ID

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

Recommendations

• Near-proper vertex 2-colorings of sparse graphs
• Maximum average degree and relaxed coloring
• \((k,j)\)-coloring of sparse graphs
• Defective 2-colorings of sparse graphs
• Coloring graphs with sparse neighborhoods

Cites work

• \((k,1)\)-coloring of sparse graphs
• \((k,j)\)-coloring of sparse graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• Improper choosability of graphs and maximum average degree
• List improper colorings of planar graphs with prescribed girth
• List Improper Colourings of Planar Graphs
• Path partitions of planar graphs
• 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

(10)

• Maximum average degree and relaxed coloring
• 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
• Relaxed equitable colorings of planar graphs with girth at least 8
• Improper coloring of sparse graphs with a given girth. II: Constructions
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• An undecidability result on limits of sparse graphs
• Defective and clustered choosability of sparse graphs

This page was built for publication: Limits of near-coloring of sparse graphs

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