Short Proofs of the Kneser-Lovász Coloring Principle

James Aisenberg, Maria Luisa Bonet, Sam Buss +2

We prove that the propositional translations of the Kneser-Lovász theorem have polynomial size extended Frege proofs and quasi-polynomial size Frege proofs. We present a new counti…