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

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. 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
Volume776
Pages (from-to)64-74
Number of pages11
ISSN0304-3975
DOIs
Publication statusPublished - 12. Jul 2019

    Fingerprint

Keywords

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

Cite this