Online coloring of hypergraphs

Magnús M. Halldórsson*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We give a tight bound on randomized online coloring of hypergraphs. The bound holds even if the algorithm knows the hypergraph in advance (but not the ordering in which it is presented). More specifically, we show that for any n and k, there is a 2-colorable k-uniform hypergraph on n vertices for which any randomized online coloring uses Ω (n / k) colors in expectation.

Original languageEnglish
Pages (from-to)370-372
Number of pages3
JournalInformation Processing Letters
Volume110
Issue number10
DOIs
Publication statusPublished - 30 Apr 2010

Other keywords

  • Graph coloring
  • Hypergraphs
  • Online algorithms

Fingerprint

Dive into the research topics of 'Online coloring of hypergraphs'. Together they form a unique fingerprint.

Cite this