# Skew-supermodular list colouring

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 for every $s \in S$ let $L_s$ be a list of k distinct positive integers. Is it true that there is a partition $\{Y_1,\dots,Y_l\}$ of S such that $i \in L_s$ for every $s \in Y_i$ (i=1,...,l), and $|\{i: Y_i \cap X \neq \emptyset\}| \geq \max\{p_1(X), p_2(X)\}$ for every $X \subseteq S$?

The conjecture was proved by Satoru Iwata and Yu Yokoi [1]. The proof uses the Sands-Sauer-Woodrow theorem.

## Remarks

If true, this would be an interesting generalization of Galvin's bipartite list-edge-colouring theorem. If $p_1=p_2=:p$, then a stronger theorem is true: the lists $L_s$ can be shorter than k, the only requirement is that for every pair of disjoint sets X,Y the number of distinct integers appearing in the lists of the elements of X is at least $p(X \cup Y)-|Y|$. To obtain the partition, it can be easily seen that if $|L_s|\gt1$ for some s, then one of the integers can be removed from $L_s$ without violating the condition.

If $p_1 \neq p_2$, a simple example on 3 nodes shows that the above condition is not sufficient. If $L_s=\{1,\dots,k\}$ for every $s \in S$, then the statement is true by the skew-supermodular variant[2] of Schrijver's Supermodular colouring theorem.

## References

1. S. Iwata, Y. Yokoi, List Supermodular Coloring, METR technical report 2016-10
2. 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.