On the choosability of complete multipartite graphs with part size three (Q1969804)

From MaRDI portal
Revision as of 16:40, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
On the choosability of complete multipartite graphs with part size three
scientific article

    Statements

    On the choosability of complete multipartite graphs with part size three (English)
    0 references
    0 references
    15 September 2000
    0 references
    Let \(K_{m*r}\) be the complete \(r\)-partite graph with \(m\) vertices in each part. \textit{P. Erdős, A. L. Rubin} and \textit{H. Taylor} [Combinatorics, graph theory and computing, Proc. West Coast Conf., Arcata/Calif. 1979, 125-157 (1980; Zbl 0469.05032)] showed that \(K_{2*r}\) is \(r\)-choosable and suggested the problem of determining the choosability of \(K_{m*r}\). The author of the present paper proves that \(K_{3*r}\) is exactly \(\lceil(4r-1)/3 \rceil\)-choosable.
    0 references
    complete \(r\)-partite graphs
    0 references
    choosability
    0 references

    Identifiers