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

DOI10.1007/S00454-017-9934-3MaRDI QIDQ1702354zbMATH OpenOpenAlexFDO

Authors 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

chromatic numbertriangle-free graphsBorsuk-Ulam theoremTucker's lemma

Mathematics Subject Classification ID

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

Abstract: In this note, we introduce a new method for constructing graphs with high chromatic number and small clique. Indeed, via this method, we present a new proof for the well-known Kneser's conjecture.

Recommendations

• On a construction of graphs with high chromatic capacity and large girth
• Large cliques in graphs with high chromatic number
• Graphs with large clique-chromatic numbers
• New bounds for the chromatic number of graphs
• Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers
• Small clique and large chromatic number
• Constructions of sparse uniform hypergraphs with high chromatic number
• New upper bounds for the chromatic number of a graph
• On graphs with small subgraphs of large chromatic number

Cites work

• scientific article; zbMATH DE number 3915223 (Why is no real title available?)
• scientific article; zbMATH DE number 3595210 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 3102257 (Why is no real title available?)
• A New Short Proof of Kneser's Conjecture
• A combinatorical proof of Kneser's conjecture
• A short proof of Kneser's conjecture
• A topological lower bound for the chromatic number of a special family of graphs
• Colorful subhypergraphs in uniform hypergraphs
• Combinatorial algebraic topology
• Combinatorial necklace splitting
• Generalized Kneser coloring theorems with combinatorial proofs
• Graph Theory and Probability
• Kneser's conjecture, chromatic number, and homotopy
• On the chromatic number of general Kneser hypergraphs
• Paths and Circuits in Critical Graphs
• Simple proofs of some Borsuk-Ulam results
• 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

Cited in

(6)

• Hedetniemi's conjecture from the topological viewpoint
• On the chromatic number of generalized Kneser hypergraphs
• On the number of star‐shaped classes in optimal colorings of Kneser graphs
• Dold's theorem from viewpoint of strong compatibility graphs
• Generalized Borsuk graphs
• A new graph parameter and a construction of larger graph without increasing radio \(k\)-chromatic number

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702354)