Paper Info
Title
Degree-constrained 2-partitions of graphs.
Abstract
A (δ≥k1,δ≥k2)-partition of a graph G is a vertex-partition (V1,V2) of G into two non-empty sets satisfying that δ(G[Vi])≥ki for i=1,2. We determine, for all positive integers k1,k2, the complexity of deciding whether a given graph has a (δ≥k1,δ≥k2)-partition.
Year
DOI
Venue
2018
10.1016/j.tcs.2018.12.023
Theoretical Computer Science
Keywords
Field
DocType
NP-complete,Polynomial time,2-partition,Minimum degree
Integer,Discrete mathematics,Graph,Combinatorics,Polynomial,Mathematics
Journal
Volume
ISSN
Citations 
776
0304-3975
0
PageRank 
References 
Authors
0.34
19
2
Name
Order
Citations
PageRank
Jørgen Bang-Jensen157368.96
Stéphane Bessy211719.68