Strengthening topological colorful results for graphs
From MaRDI portal
Publication:2359976
Abstract: Various results ensure the existence of large complete bipartite graphs in properly colored graphs when some condition related to a topological lower bound on the chromatic number is satisfied. We generalize three theorems of this kind, respectively due to Simonyi and Tardos (Combinatorica, 2006), Simonyi, Tardif, and Zsb'an (The Electronic Journal of Combinatorics, 2013), and Chen (Journal of Combinatorial Theory, Series A, 2011). As a consequence of the generalization of Chen's theorem, we get new families of graphs whose chromatic number equals their circular chromatic number and that satisfy Hedetniemi's conjecture for the circular chromatic number.
Recommendations
Cites work
- scientific article; zbMATH DE number 3862930 (Why is no real title available?)
- scientific article; zbMATH DE number 3728320 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- A certain combinatorial inequality
- A combinatorial proof for the circular chromatic number of Kneser graphs
- A course in topological combinatorics
- A generalization of Tucker's combinatorial lemma with topological applications
- A new coloring theorem of Kneser graphs
- A short proof for Chen's alternative Kneser coloring lemma
- A survey on Hedetniemi's conjecture
- A topological lower bound for the circular chromatic number of Schrijver graphs
- Acyclic graph coloring and the complexity of the star chromatic number
- Circular chromatic number of Kneser graphs
- Circular chromatic number: A survey
- Colorful subgraphs in Kneser-like graphs
- Colorful subhypergraphs in Kneser hypergraphs
- Colourful theorems and indices of homomorphism complexes
- Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
- Graph powers and graph homomorphisms
- Graphs whose circular chromatic number equals the chromatic number
- Hedetniemi's conjecture for Kneser hypergraphs
- Kneser's conjecture, chromatic number, and homotopy
- Local chromatic number, Ky Fan's theorem, and circular colorings
- Multichromatic numbers, star chromatic numbers and Kneser graphs
- On the b-chromatic number of Kneser graphs
- On the cancellation law among finite relational structures
- On the chromatic number of general Kneser hypergraphs
- On the diameter of Kneser graphs
- Operations with structures
- Recent developments in circular colouring of graphs
- Star chromatic numbers and products of graphs
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- Topological lower bounds for the chromatic number: a hierarchy
- 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
- n-tuple colorings and associated graphs
Cited in
(10)- Colourful theorems and indices of homomorphism complexes
- Coloring properties of categorical product of general Kneser hypergraphs
- Chromatic number of random Kneser hypergraphs
- On the number of star‐shaped classes in optimal colorings of Kneser graphs
- Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
- Topological bounds for graph representations over any field
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Circular chromatic number of induced subgraphs of Kneser graphs
- Colorful subhypergraphs in uniform hypergraphs
- Colorings of complements of line graphs
This page was built for publication: Strengthening topological colorful results for graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2359976)
