Thumbnail

Decomposition of graphs: some polynomial cases

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003), Decomposition of graphs: some polynomial cases. https://basepub.dauphine.fr/handle/123456789/3938

View/Open
Type
Document de travail / Working paper
Date
2003
Series title
Note de recherche du LAMSADE
Pages
11
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel
Abstract (EN)
We study the problem of decomposing the vertex set V of a graphinto two parts (V1, V2) which induce subgraphs where each vertex vin V1 has degree at least a(v) and each vertex v in V2 has degreeat least b(v). We investigate several polynomial cases of this NP-complete problem. We give a polynomial-time algorithm for graphswith bounded treewidth which decides if a graph admits a decom-position and gives such a decomposition if it exists. We also givepolynomial-time algorithms that always find a decomposition for thefollowing two cases : triangle-free graphs such that d(v) ≥ a(v) + b(v)for all v ∈ V and graphs with girth at least 5 such that d(v) ≥a(v) + b(v) − 1 for all v ∈ V .
Subjects / Keywords
Polynomial Algorithm; treewidth; girth; Graph; Decomposition; Complexity; degree constraints