
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 paperDate
2003Series title
Note de recherche du LAMSADEPages
11
Metadata
Show full item recordAbstract (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 constraintsRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2006) Article accepté pour publication ou publié
-
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) Communication / Conférence
-
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2007) Article accepté pour publication ou publié
-
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2010) Article accepté pour publication ou publié
-
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) Document de travail / Working paper