On the choice number of complete multipartite graphs with part size four
| Autor: | Kierstead, H. A., Salmon, Andrew, Wang, Ran |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. |
| Databáze: | arXiv |
| Externí odkaz: |
|