Degree-constrained 2-partitions of graphs

Jørgen Bang-Jensen, Stéphane Bessy*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


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. We also address the problem of finding a function g(k1,k2) such that the (δ≥k1,δ≥k2)-partition problem is NP-complete for the class of graphs of minimum degree less than g(k1,k2) and polynomial time solvable for all graphs with minimum degree at least g(k1,k2). We prove that g(1,k) exists and has value k for all k≥3, that g(2,2) also exists and has value 3 and that g(2,3), if it exists, has value 4 or 5.

Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)64-74
Number of pages11
Publication statusPublished - 12. Jul 2019



  • 2-partition
  • Minimum degree
  • NP-complete
  • Polynomial time

Cite this