# Skew-supermodular colouring with prescribed class-sizes

Let $p_1$ and $p_2$ be integer skew-supermodular set functions on ground set S such that $\max\{p_1(X),p_2(X)\}\leq \min\{|X|,k\}$ for every $X \subseteq S$, and let us be given k nonnegative integers $n_1,n_2,\dots,n_k$. Decide whether there is a good colouring of $S$ with these class sizes, that is a partition $\{Y_1,\dots,Y_k\}$ of S such that $|\{i: Y_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$, and $|Y_i| = n_i$ 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 $G=(V,E)$ and two positive integers $a,b$, decide if $E$ can be partitioned into a perfect matching, a matching of size $a$, and a matching of size $b$.

## Remarks

If the class sizes are almost equal (that is $|n_i-n_j|\le 1$ for every $1\le i\ltj\le k$) 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 $d_G(v)\le k$ for every $v\in A\cup B$, and k positive integers $n_1,n_2,\dots,n_k$ satisfying $n_1+n_2+\dots+n_k = |E|$. Does there exist k disjoint matchings $M_1,M_2,\dots,M_k\subseteq E$ such that $|M_i| = n_i$ for every i=1,...,k? This is also NP-complete by [2], but if the list $n_1,n_2,\dots,n_k$ 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

1. R.R. Kamalian, V.V. Mkrtchyan, On complexity of special maximum matchings constructing, DOI link, arXiv link
2. D. Pálvölgyi, Partitioning to three matchings of given size is NP-complete for bipartite graphs, EGRES Quick Proof no. 2013-01
3. 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.
4. J. Folkman, D.R. Fulkerson, Edge colorings in bipartite graphs, Combinatorial mathematics and its applications, University of North Carolina Press, Chapel Hill (1969).