Skew-supermodular list colouring

From Egres Open
Jump to: navigation, search

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]?

Solved c.jpg

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


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.


  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.