On the choice number of complete multipartite graphs with part size four

2014/07/14 by H. A. Kierstead, Kierstead, H. A., Andrew Salmon +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1407.3817

arxiv created 2014/07/14 · arxiv updated 2014/07/16

Abstract

Let 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ős, Rubin, and Taylor showed that ch( K_2*k)=k, and suggested the problem of determining the choice number of K_s*k. The first author established ch( K_3*k)=\lceil (4k-1)/(3)\rceil. Here we prove ch (K_4*k)=\lceil (3k-1)/(2)\rceil.

Related

• On the asymptotic value of the choice number of complete multi-partite graphs
• On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach
• Choice numbers of graphs
• Beyond Ohba's Conjecture: A bound on the choice number of k-chromatic graphs with n vertices
• Towards on-line Ohba's conjecture