Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
From MaRDI portal
Publication:3055928
DOI10.1002/jgt.20467zbMath1209.05177OpenAlexW4231799266MaRDI QIDQ3055928
Mickaël Montassier, Pascal Ochem, Anna O. Ivanova, Oleg V. Borodin, Andre Raspaud
Publication date: 10 November 2010
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20467
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)
Related Items (30)
A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ Every planar graph with girth at least 5 is \((1,9)\)-colorable ⋮ Defective 2-colorings of planar graphs without 4-cycles and 5-cycles ⋮ Fractional, Circular, and Defective Coloring of Series-Parallel Graphs ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Colouring planar graphs with bounded monochromatic components ⋮ On 1-improper 2-coloring of sparse graphs ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ Decomposition of sparse graphs into two forests, one having bounded maximum degree ⋮ \((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 ⋮ \((k,j)\)-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 ⋮ Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests ⋮ On 2-defective DP-colorings of sparse graphs ⋮ Defective DP-colorings of sparse multigraphs ⋮ Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1 ⋮ Planar graphs with girth at least 5 are \((3, 5)\)-colorable ⋮ List strong linear 2-arboricity of sparse graphs ⋮ Defective DP-colorings of sparse simple graphs ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ Defective and clustered choosability of sparse graphs ⋮ Planar graphs with girth at least 5 are \((3, 4)\)-colorable ⋮ Vertex Partitions into an Independent Set and a Forest with Each Component Small ⋮ Limits of Near-Coloring of Sparse Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers
- Every planar map is four colorable. I: Discharging
- Every planar map is four colorable. II: Reducibility
- On the maximum average degree and the oriented chromatic number of a graph
- List edge and list total colourings of multigraphs
- Homomorphisms from sparse graphs with large girth.
- Path partitions of planar graphs
- Oriented 5-coloring of sparse plane graphs
- On the total coloring of planar graphs.
- List Improper Colourings of Planar Graphs
- Edge-partitions of planar graphs and their game coloring numbers
- Improper choosability of graphs and maximum average degree
This page was built for publication: Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
