# Skew-supermodular list colouring

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

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 [math]p_1=p_2=:p[/math], then a stronger theorem is true: the lists [math]L_s[/math] 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 [math]p(X \cup Y)-|Y|[/math]. To obtain the partition, it can be easily seen that if [math]|L_s|\gt1[/math] for some *s*, then one of the integers can be removed from [math]L_s[/math] without violating the condition.

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

## References

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