Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

DOI10.1134/S0037446611050041zbMath1232.05073MaRDI QIDQ665888

Alexandr V. Kostochka, Oleg V. Borodin

Publication date: 7 March 2012

Published in: Siberian Mathematical Journal (Search for Journal in Brave)

zbMATH Keywords

planar graphsgirthcoloring

Mathematics Subject Classification ID

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

Related Items (22)

A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ On 1-improper 2-coloring of sparse graphs ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs ⋮ \((k,1)\)-coloring of sparse graphs ⋮ On the vertex partitions of sparse graphs into an independent vertex set and a forest with bounded maximum degree ⋮ 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 ⋮ Planar graphs with girth at least 5 are \((3, 5)\)-colorable ⋮ Defective DP-colorings of sparse simple graphs ⋮ A Complexity Dichotomy for the Coloring of Sparse 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 ⋮ Planar graphs with girth at least 5 are \((3, 4)\)-colorable ⋮ Vertex Partitions into an Independent Set and a Forest with Each Component Small ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5 ⋮ Limits of Near-Coloring of Sparse Graphs

Cites Work

• 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
• Improper choosability of graphs and maximum average degree
• Unnamed Item

This page was built for publication: Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1