1
$\begingroup$

This statement is proved by Vizing and Erdos & Rubin (page 30) independently.
But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'.
I think it is related to the proof of the following statement

$K_{2,r}$ is $r$-choosable.

as Erdos & Rubin's paper mentioned.
But I have no idea with how to prove the generalized one.
Would you help me?

$\endgroup$

1 Answer 1

1
$\begingroup$

Assume that $K_{k,m}$ is not $k$-choosable with some lists of admissible colors. Let $A_1$, $A_2$, $\ldots$, $A_k$ be sets of admissible colors in the small part (that with $k$ vertices). Choose arbitrarily colors $a_i\in A_i$ for all $i=1,\ldots,k$. The large part must contain a vertex with admissible colors $a_1,\ldots,a_k$, otherwise we may color each vertex in the large part. This yields that all $a_i$'s are distinct, in other words all $A_i$'s must be disjoint. Then all sequences $(a_1,\ldots,a_k)$ are different, and the large part must contain $k^k$ distinct vertices. On the other hand, if $m=k^k$, all $A_i$'s are indeed disjoint, and the large part contain all such $k^k$ vertices, we can not color it.

$\endgroup$
1
  • $\begingroup$ Wow, it's more straightforward than I thought. Thanks a lot! $\endgroup$
    – okw1124
    Oct 29, 2021 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.