On a theorem of Erdos, Rubin, and Taylor on choosability of complete bipartite graphs

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-4
Number of pages4
JournalElectronic Journal of Combinatorics
Volume9
Issue number1 N
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On a theorem of Erdos, Rubin, and Taylor on choosability of complete bipartite graphs'. Together they form a unique fingerprint.

Cite this