# Degree-constrained 2-partitions of graphs

arXiv: https://arxiv.org/abs/1801.06216 · HTML: https://mlsanity.com/paper/1801.06216/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2018.

## Built on by (most cited first, 1 of 1)

- [The Complexity of Manipulation of k-Coalitional Games on Graphs](https://mlsanity.com/paper/2408.07368/) (2024)

## Abstract (arXiv)

A (δ≥ k1,δ≥ k2)-partition of a graph G is a vertex-partition (V1,V2) of G 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 cal NP-complete for the class of graphs of minimum degree less than g(k1,k2) and polynomial for all graphs with minimum degree at least g(k1,k2). We prove that g(1,k)=k for k≥ 3, that g(2,2)=3 and that g(2,3), if it exists, has value 4 or 5.