Efficient algorithms for decomposing graphs under degree constraints
type: Item
instance of: scholarly article
title: Efficient algorithms for decomposing graphs under degree constraints
zbMATH Open document ID: 1131.05068
author: Cristina Bazgan
author: Daniel Vanderpooten
author: Zsolt Tuza
published in: Discrete Applied Mathematics
publication date: 2007-05-30T00:00:00Z
review text: In the paper efficient algorithms for finding \((a,b)\)-decompositions of graphs are presented. Let \(G=(V,E)\) be a graph and \(a,b : V(G)\rightarrow\mathbb N\) two functions such that \(d(v) \geq a(v) + b(v) +1\) of every vertex \(v\) of \(G\). It is known that there exists a partition \((A,B)\) of \(V\) such that \(d_A(v)\geq a(v)\) for each \(v \in A\) and \(d_B(v)\geq b(v)\) for each \(v \in B\). This partition is called \((a,b)\)-decomposition. The authors prove that when \(G\) does not contain a \(3\)-cycle and \(d(v) \geq a(v) + b(v)\) for each \(v \in V\), then there exists an \((a,b)\)-decomposition, and when \(G\) does not contain a \(3\)-cycle or \(4\)-cycle and \(d(v) \geq a(v) + b(v)-1\) for each \(v \in V\), then there exists also an \((a,b)\)-decomposition. The authors also present algorithms with polynomial complexity for finding \((a,b)\)-decompositions of graph \(G\) in all three cases mentioned above.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5159560
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
full work available at URL: j.dam.2006.10.005
OpenAlex ID: W2027624833
cites work: Algorithms and Computation
cites work: The satisfactory partition problem
cites work: Recognizing decomposable graphs
cites work: Decomposing graphs with girth at least five under degree constraints
cites work: Über eine von H. S. WILF angegebene Schranke für die chromatische Zahl endlicher Graphen
cites work: Q4820779
cites work: On decomposition of triangle-free graphs under degree constraints
cites work: Q4715286
DOI: 10.1016/J.DAM.2006.10.005
description: scientific article; zbMATH DE number 5159560