\((k,j)\)-coloring of sparse graphs

DOI10.1016/J.DAM.2011.06.021zbMath1239.05059OpenAlexW1508498053MaRDI QIDQ411834

Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, Andre Raspaud

Publication date: 30 April 2012

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

Full work available at URL: https://doi.org/10.1016/j.dam.2011.06.021

zbMATH Keywords

linear programmingvertex partitionmaximum average degreedischarging proceduresubgraphs with bounded maximum degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Linear programming (90C05) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07) Density (toughness, etc.) (05C42)

Related Items (10)

On 1-improper 2-coloring of sparse graphs ⋮ Sparse critical graphs for defective DP-colorings ⋮ Defective 2-colorings of sparse graphs ⋮ (1,k)-Coloring of Graphs with Girth at Least Five on a Surface ⋮ 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 ⋮ Defective and clustered choosability of sparse graphs ⋮ Limits of Near-Coloring of Sparse Graphs

Cites Work

• \((k,1)\)-coloring of sparse graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• 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
• Linear Programming
• Improper choosability of graphs and maximum average degree
• Unnamed Item
• Unnamed Item
• Unnamed Item

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