Efficient algorithms for decomposing graphs under degree constraints (Q881575): Difference between revisions

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.