On the CNF-complexity of bipartite graphs containing no 's
arXiv:1206.6068
Abstract
By a probabilistic construction, we find a bipartite graph having average degree which can be expressed as a conjunctive normal form using clauses. This contradicts research problem 1.33 of Jukna.
arXiv comment6 pages