(k,1)-coloring of sparse graphs

DOI10.1016/J.DISC.2011.11.031MaRDI QIDQ409448zbMATH OpenOpenAlexFDO

Authors Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, André Raspaud

Publication date 13 April 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2011.11.031

zbMATH Keywords

improper coloringbounded maximum average degreedischarging procedure with global approach

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Recommendations

• On 1-improper 2-coloring of sparse graphs
• Near-proper vertex 2-colorings of sparse graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
• \((k,j)\)-coloring of sparse graphs

Cites work

• scientific article; zbMATH DE number 6004909 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• Circular \((5,2)\)-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
• Improper choosability of graphs and maximum average degree
• List Improper Colourings of Planar Graphs
• Near-proper vertex 2-colorings of sparse graphs
• On the total coloring of planar graphs.
• Oriented 5-coloring of sparse plane 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

(24)

• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• \((k,j)\)-coloring of sparse graphs
• \(k\)-forested 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
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
• Near-proper vertex 2-colorings of sparse graphs
• On 1-improper 2-coloring of sparse graphs
• On 2-defective DP-colorings of sparse graphs
• Coloring, sparseness and girth
• Defective 2-colorings of sparse graphs
• Improper coloring of sparse graphs with a given girth. II: Constructions
• List strong linear 2-arboricity of sparse graphs
• \(k\)-forested choosability of planar graphs and sparse graphs
• A GRASP for coloring sparse graphs
• Sparse critical graphs for defective DP-colorings
• Every planar graph with girth at least 5 is (1,9)-colorable
• Limits of near-coloring of sparse graphs
• Defective and clustered choosability of sparse graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Sparse \(H\)-colourable graphs of bounded maximum degree
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs
• A Complexity Dichotomy for the Coloring of Sparse Graphs

This page was built for publication: \((k,1)\)-coloring of sparse graphs

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