## Abstract

A (δ≥k_{1},δ≥k_{2})-partition of a graph G is a vertex-partition (V_{1},V_{2}) of G into two non-empty sets satisfying that δ(G[V_{i}])≥k_{i} for i=1,2. We determine, for all positive integers k_{1},k_{2}, the complexity of deciding whether a given graph has a (δ≥k_{1},δ≥k_{2})-partition. We also address the problem of finding a function g(k_{1},k_{2}) such that the (δ≥k_{1},δ≥k_{2})-partition problem is NP-complete for the class of graphs of minimum degree less than g(k_{1},k_{2}) and polynomial time solvable for all graphs with minimum degree at least g(k_{1},k_{2}). 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 language | English |
---|---|

Journal | Theoretical Computer Science |

Volume | 776 |

Pages (from-to) | 64-74 |

Number of pages | 11 |

ISSN | 0304-3975 |

DOIs | |

Publication status | Published - 12. Jul 2019 |

## Keywords

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