Erdos, Rubin, and Taylor found a nice correspondence between the minimum order of a complete bipartite graph that is not r-choosable and the minimum number of edges in an r-uniform hypergraph that is not 2-colorable (in the ordinary sense). In this note we use their ideas to derive similar correspondences for complete k-partite graphs and complete k-uniform k-partite hypergraphs.
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics