New construction of graphs with high chromatic number and small clique number

DOI10.1007/s00454-017-9934-3zbMath1382.05024arXiv1702.01390OpenAlexW3098545910MaRDI QIDQ1702354

Hamid Reza Daneshpajouh

Publication date: 28 February 2018

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Borsuk-Ulam theoremchromatic numbertriangle-free graphsTucker's lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Hedetniemi's conjecture from the topological viewpoint ⋮ On the number of star‐shaped classes in optimal colorings of Kneser graphs ⋮ Dold's theorem from viewpoint of strong compatibility graphs ⋮ On the chromatic number of generalized Kneser hypergraphs

Cites Work

• On the chromatic number of general Kneser hypergraphs
• Colorful subhypergraphs in uniform hypergraphs
• Kneser's conjecture, chromatic number, and homotopy
• A short proof of Kneser's conjecture
• Generalized Kneser coloring theorems with combinatorial proofs
• A topological lower bound for the chromatic number of a special family of graphs
• A combinatorical proof of Kneser's conjecture
• Combinatorial necklace splitting
• Graph Theory and Probability
• Simple proofs of some Borsuk-Ulam results
• A New Short Proof of Kneser's Conjecture
• Paths and Circuits in Critical Graphs
• Sur le coloriage des graphs
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Combinatorial algebraic topology
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New construction of graphs with high chromatic number and small clique number