# 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 ^{[1]}, and independently by Dömötör Pálvölgyi ^{[2]}, 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^{[3]} 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 ^{[2]}, 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 ^{[4]}. A generalization of this for supermodular colouring is posed as an open question: Skew-supermodular colouring with two class sizes.

## References

- ↑ R.R. Kamalian, V.V. Mkrtchyan,
*On complexity of special maximum matchings constructing*, DOI link, arXiv link - ↑
^{2.0}^{2.1}D. Pálvölgyi,*Partitioning to three matchings of given size is NP-complete for bipartite graphs*, EGRES Quick Proof no. 2013-01 - ↑ A. Bernáth, T. Király,
*Covering skew-supermodular functions by hypergraphs of minimum total size*, Operations Research Letters 37 (2009), 345-350. DOI link, EGRES Technical Report. - ↑ J. Folkman, D.R. Fulkerson,
*Edge colorings in bipartite graphs*, Combinatorial mathematics and its applications, University of North Carolina Press, Chapel Hill (1969).