Recognition: unknown
On the choice number of complete multipartite graphs with part size four
classification
🧮 math.CO
keywords
mathrmchoicenumbercompletefracgraphlceilleft
read the original abstract
Let $\mathrm{ch}(G)$ denote the choice number of a graph $G$, and let $K_{s*k}$ be the complete $k$-partite graph with $s$ vertices in each part. Erd\H{o}s, Rubin, and Taylor showed that $\mathrm{ch}( K_{2*k})=k$, and suggested the problem of determining the choice number of $K_{s*k}.$ The first author established $\mathrm{ch}( K_{3*k})=\left\lceil \frac{4k-1}{3}\right\rceil$. Here we prove $\mathrm{ch} (K_{4*k})=\left\lceil \frac{3k-1}{2}\right\rceil$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.