New construction of graphs with high chromatic number and small clique number
From MaRDI portal
Publication:1702354
DOI10.1007/S00454-017-9934-3zbMATH Open1382.05024arXiv1702.01390OpenAlexW3098545910MaRDI QIDQ1702354FDOQ1702354
Publication date: 28 February 2018
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1702.01390
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
- Distance graphs with large chromatic numbers and small clique numbers
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph Theory and Probability
- 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
- Kneser's conjecture, chromatic number, and homotopy
- A short proof of Kneser's conjecture
- Title not available (Why is that?)
- A New Short Proof of Kneser's Conjecture
- Title not available (Why is that?)
- Generalized Kneser coloring theorems with combinatorial proofs
- A combinatorical proof of Kneser's conjecture
- Simple proofs of some Borsuk-Ulam results
- On the chromatic number of general Kneser hypergraphs
- Paths and Circuits in Critical Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Colorful subhypergraphs in uniform hypergraphs
- A topological lower bound for the chromatic number of a special family of graphs
- Combinatorial necklace splitting
Cited In (6)
- On the chromatic number of generalized Kneser hypergraphs
- On the number of star‐shaped classes in optimal colorings of Kneser graphs
- A new graph parameter and a construction of larger graph without increasing radio \(k\)-chromatic number
- Generalized Borsuk graphs
- Dold's theorem from viewpoint of strong compatibility graphs
- Hedetniemi's conjecture from the topological viewpoint
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)
