Sí, $K_{10,10}$ est $4$ -elegible.
El artículo "Choosability in Graphs" de Erdos, Rubin y Taylor relaciona $\chi_l(K_{m,n})$ a $2$ -(también conocida como propiedad B en la literatura). Un hipergrafo tiene la propiedad B si podemos $2$ -colorear sus aristas de modo que ninguna arista sea monocromática. Escribimos $m(k)$ para el número mínimo de aristas en un $k$ -hipergrama uniforme que hace no tienen la propiedad B - en otras palabras, cualquier conjunto $S$ que interseca cada arista debe contener alguna arista.
Erdos, Rubin y Taylor lo demuestran:
Hecho 1. El grafo bipartito completo $K_{m(k), m(k)}$ no es $k$ -elegible.
Prueba. Toma un $k$ -hipergrama uniforme $\mathcal H$ con $m(k)$ aristas que no tengan la propiedad B, y utilizar $E(\mathcal H$ ) como las listas de colores a cada lado de $K_{m(k),m(k)}$ . Supongamos que coloreamos todos los vértices de un lado del grafo bipartito; sea $S$ sea el conjunto de colores utilizados. Entonces $S$ debe intersecar todas las aristas de $\mathcal H$ porque cada vértice tiene un color. Por lo tanto $S$ contiene una arista de $\mathcal H$ el vértice correspondiente del otro lado no se puede colorear.
Hecho 2. Si $a + b < m(k)$ entonces el grafo bipartito completo $K_{a,b}$ est $k$ -elegible.
Prueba. Para cualquier $k$ -asignación de lista de $K_{a,b}$ , dejemos que $\mathcal H$ sea el hipergrafo cuyas aristas son las listas de colores de ambos lados. (Si las listas de colores se repiten, no pasa nada; sólo necesitamos incluir la arista una vez.) Puesto que $\mathcal H$ tiene como máximo $a+b$ bordes, tiene la propiedad B, así que vamos a $2$ -colorear los vértices de $\mathcal H$ rojo y azul para que cada arista tenga un vértice rojo y un vértice azul.
Para obtener una coloración de lista, elija los colores de la siguiente manera: para cada vértice del primer lado de $K_{a,b}$ elija un color tal que el vértice correspondiente de $\mathcal H$ es rojo. Para cada vértice del segundo lado de $K_{a,b}$ elija un color tal que el vértice correspondiente de $\mathcal H$ es azul.
Erdos, Rubin y Taylor ya sabían que $m(1)=1$ , $m(2)=3$ y $m(3)=7$ . Esto demuestra, por ejemplo, que no sólo $K_{10,10}$ pero incluso $K_{7,7}$ no es $3$ -elegible. Utilice las siguientes listas de colores en cada lado de $K_{7,7}$ : $$\{1,2,3\}\;\{1,4,5\}\;\{1,6,7\}\; \{2,4,6\}\; \{2,5,7\}\; \{3,4,7\}\; \{3,5,6\}$$ Se basan en la Plano de Fano que es el hipergrafo que nos da $m(3)=7$ : si se elige un punto en cada línea del plano de Fano, existe alguna línea en la que se eligen todos los puntos.
Un artículo más reciente, "Sobre el tamaño mínimo de hipergrafos 4-uniformes sin propiedad $B$ " de Patric Östergård, muestra que $m(4) = 23$ . De ello se deduce que siempre que $a+b < 23$ , $K_{a,b}$ est $4$ -elegible; en particular, $K_{10,10}$ (e incluso $K_{11,11})$ est $4$ -elegible.
