Decomposition of sparse graphs, with application to game coloring number

DOI10.1016/J.DISC.2010.01.008zbMATH Open1219.05145OpenAlexW2150898108MaRDI QIDQ968426FDOQ968426

Authors: Mickaël Montassier, Arnaud Pêcher, Douglas B. West, Xuding Zhu, André Raspaud 

Publication date: 5 May 2010

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

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

Recommendations

• Decomposition of sparse graphs into two forests, one having bounded maximum degree
• \(k\)-forested coloring of sparse graphs
• On the game coloring index of \(F^+\)-decomposable graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
• Acyclic edge-colorings of sparse graphs

zbMATH Keywords

forestgame coloring numbersubgraphs with bounded maximum degreeedge-partition

Mathematics Subject Classification ID

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

Cites Work

• Decomposition of Finite Graphs Into Forests
• Title not available (Why is that?)
• Covering planar graphs with forests, one having bounded maximum degree
• Covering planar graphs with forests
• ON THE COMPLEXITY OF SOME COLORING GAMES
• The game coloring number of planar graphs
• Refined activation strategy for the marking game
• Edge-partitions of planar graphs and their game coloring numbers
• Decomposing a planar graph with girth 9 into a forest and a matching

Cited In (12)

• Game chromatic number of graphs with locally bounded number of cycles
• Decomposition of sparse graphs into two forests, one having bounded maximum degree
• Decomposition of sparse graphs into forests and a graph with bounded degree
• Degree bounded forest covering
• Decomposing a graph into forests and a matching
• Decomposing 4-connected planar triangulations into two trees and one path
• Decomposition of sparse graphs into forests: the nine dragon tree conjecture for \(k \leq 2\)
• Title not available (Why is that?)
• Sparse hypergraphs and pebble game algorithms
• On the game coloring index of \(F^+\)-decomposable graphs
• Decomposing a graph into pseudoforests with one having bounded degree
• Decomposing a graph into forests

This page was built for publication: Decomposition of sparse graphs, with application to game coloring number

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