Short Proofs of the Kneser-Lovász Coloring Principle

DOI10.1007/978-3-662-47666-6_4zbMath1443.03041arXiv1505.05531OpenAlexW2963581229WikidataQ60512040 ScholiaQ60512040MaRDI QIDQ3449464

James Aisenberg, Adrian Crǎciun, Maria Luisa Bonet, Samuel R. Buss, Gabriel I. Istrate

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1505.05531

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Complexity of proofs (03F20)

Related Items (2)

Short proofs of the Kneser-Lovász coloring principle ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Propositional proofs and reductions between NP search problems
• Kneser's conjecture, chromatic number, and homotopy
• Generalized Kneser coloring theorems with combinatorial proofs
• A combinatorical proof of Kneser's conjecture
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Quasipolynomial size proofs of the propositional pigeonhole principle
• QUASIPOLYNOMIAL SIZE FREGE PROOFS OF FRANKL’S THEOREM ON THE TRACE OF SETS
• Proof Complexity and the Kneser-Lovász Theorem
• Polynomial size proofs of the propositional pigeonhole principle
• The relative efficiency of propositional proof systems
• The Complexity of Propositional Proofs

This page was built for publication: Short Proofs of the Kneser-Lovász Coloring Principle