Strengthening topological colorful results for graphs
From MaRDI portal
Publication:2359976
DOI10.1016/J.EJC.2017.03.011zbMATH Open1365.05081arXiv1606.02544OpenAlexW2411195307MaRDI QIDQ2359976FDOQ2359976
Authors: Meysam Alishahi, Hossein Hajiabolhassan, Frédéric Meunier 
Publication date: 23 June 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1606.02544
Recommendations
Cites Work
- Graph powers and graph homomorphisms
- On the diameter of Kneser graphs
- Title not available (Why is that?)
- 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
- Kneser's conjecture, chromatic number, and homotopy
- A survey on Hedetniemi's conjecture
- Colorful subgraphs in Kneser-like graphs
- Local chromatic number, Ky Fan's theorem, and circular colorings
- Title not available (Why is that?)
- Recent developments in circular colouring of graphs
- Star chromatic numbers and products of graphs
- Acyclic graph coloring and the complexity of the star chromatic number
- Circular chromatic number: A survey
- n-tuple colorings and associated graphs
- Circular chromatic number of Kneser graphs
- A short proof for Chen's alternative Kneser coloring lemma
- A new coloring theorem of Kneser graphs
- A generalization of Tucker's combinatorial lemma with topological applications
- A combinatorial proof for the circular chromatic number of Kneser graphs
- Multichromatic numbers, star chromatic numbers and Kneser graphs
- A topological lower bound for the circular chromatic number of Schrijver graphs
- Topological lower bounds for the chromatic number: a hierarchy
- Title not available (Why is that?)
- Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
- Colorful subhypergraphs in Kneser hypergraphs
- On the chromatic number of general Kneser hypergraphs
- On the b-chromatic number of Kneser graphs
- A certain combinatorial inequality
- A course in topological combinatorics
- Colourful theorems and indices of homomorphism complexes
- On the cancellation law among finite relational structures
- Hedetniemi's conjecture for Kneser hypergraphs
- Operations with structures
- The Borsuk--Ulam-property, Tucker-property and constructive proofs in combinatorics
- Graphs whose circular chromatic number equals the chromatic number
Cited In (10)
- Coloring properties of categorical product of general Kneser hypergraphs
- Colourful theorems and indices of homomorphism complexes
- On the number of star‐shaped classes in optimal colorings of Kneser graphs
- Chromatic number of random Kneser hypergraphs
- 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)
