Skew-supermodular colouring with prescribed class-sizes

Let [math]p_1[/math] and [math]p_2[/math] be integer skew-supermodular set functions on ground set S such that [math]\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}[/math] for every [math]X \subseteq S[/math], and let us be given k nonnegative integers [math]n_1,n_2,\dots,n_k[/math]. Decide whether there is a good colouring of [math]S[/math] with these class sizes, that is a partition [math]\{Y_1,\dots,Y_k\}[/math] of S such that [math]|\{i: Y_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}[/math] for every [math]X \subseteq S[/math], and [math]|Y_i| = n_i[/math] for every i=1,...,k?

It was shown by R.R. Kamalian and V.V. Mkrtchyan , and independently by Dömötör Pálvölgyi , that the following special case is already NP-complete: Given a subcubic bipartite graph [math]G=(V,E)[/math] and two positive integers [math]a,b[/math], decide if [math]E[/math] can be partitioned into a perfect matching, a matching of size [math]a[/math], and a matching of size [math]b[/math].

Remarks

If the class sizes are almost equal (that is [math]|n_i-n_j|\le 1[/math] for every [math]1\le i\ltj\le k[/math]) then the answer to the above question is always YES by the skew-supermodular variant of Schrijver's Supermodular colouring theorem.

A special case of this problem is the following: given a bipartite graph G=(A,B,E) with [math] d_G(v)\le k[/math] for every [math]v\in A\cup B[/math], and k positive integers [math]n_1,n_2,\dots,n_k[/math] satisfying [math]n_1+n_2+\dots+n_k = |E|[/math]. Does there exist k disjoint matchings [math]M_1,M_2,\dots,M_k\subseteq E[/math] such that [math]|M_i| = n_i[/math] for every i=1,...,k? This is also NP-complete by , but if the list [math]n_1,n_2,\dots,n_k[/math] contains at most two distinct positive integers, then there is a characterization and an algorithm by a result of Folkman and Fulkerson . A generalization of this for supermodular colouring is posed as an open question: Skew-supermodular colouring with two class sizes.