Exponential Lower Bounds for the Tree-Like Hajós Calculus
Lists
Only you see this
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...