Efficient algorithms for decomposing graphs under degree constraints

DOI10.1016/j.dam.2006.10.005zbMath1131.05068OpenAlexW2027624833MaRDI QIDQ881575

Cristina Bazgan, Daniel Vanderpooten, Zsolt Tuza

Publication date: 30 May 2007

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

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

On partitions of graphs under degree constraints ⋮ Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ On a conjecture of Schweser and Stiebitz ⋮ On connected partition with degree constraints ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ Partitions of graphs and multigraphs under degree constraints ⋮ Degree-constrained 2-partitions of graphs ⋮ A note on partitions of graphs under degree constraints ⋮ On the existence of vertex-disjoint subgraphs with high degree sum ⋮ Improper C-colorings of graphs ⋮ Unnamed Item ⋮ Graph partitions under average degree constraint ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ On non-trivial Nash stable partitions in additive hedonic games with symmetric 0/1-utilities ⋮ Partitions of multigraphs under minimum degree constraints ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Satisfactory graph partition, variants, and generalizations ⋮ A generalization of Stiebitz-type results on graph decomposition ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs ⋮ Partitions of multigraphs without \(C_4\)

Cites Work

• The satisfactory partition problem
• Recognizing decomposable graphs
• On decomposition of triangle-free graphs under degree constraints
• Decomposing graphs with girth at least five under degree constraints
• Algorithms and Computation
• Über eine von H. S. WILF angegebene Schranke für die chromatische Zahl endlicher Graphen
• Unnamed Item
• Unnamed Item

This page was built for publication: Efficient algorithms for decomposing graphs under degree constraints