Exponential Lower Bounds for the Tree-Like Hajós Calculus

Kazuo Iwama, Toniann PitassiInf. Process. Lett 1995 · OpenReview

Abstract

The Hajós Calculus is a simple, nondeterministic procedure which generates precisely the class of non-3-colorable graphs. In this note, we prove exponential lower bounds on the size of tree-like Hajós constructions.
BibTeX
@inproceedings{iwama1995exponential,
  author = {Kazuo Iwama and Toniann Pitassi},
  title = {{Exponential Lower Bounds for the Tree-Like Hajós Calculus}},
  booktitle = {Inf. Process. Lett},
  year = {1995},
  url = {https://openreview.net/forum?id=YeRVyM0ELQ},
}

Loading related content...

Figure