Efficient algorithms for decomposing graphs under degree constraints (Q881575)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Efficient algorithms for decomposing graphs under degree constraints
scientific article

    Statements

    Efficient algorithms for decomposing graphs under degree constraints (English)
    0 references
    0 references
    0 references
    0 references
    30 May 2007
    0 references
    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.
    0 references

    Identifiers