On the chromatic number of general Kneser hypergraphs

DOI10.1016/J.JCTB.2015.05.010zbMATH Open1319.05046arXiv1302.5394OpenAlexW585142893MaRDI QIDQ490992FDOQ490992

Hossein Hajiabolhassan, Meysam Alishahi

Publication date: 21 August 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In this paper, in view of $Z_p$-Tucker lemma, we introduce a lower bound for chromatic number of Kneser hypergraphs which improves Dol'nikov-K{v{r}}{'{i}}{v{z}} bound. Next, we introduce multiple Kneser hypergraphs and we specify the chromatic number of some multiple Kneser hypergraphs. For a vector of positive integers $vecs=(s_1,s_2,ldots,s_m)$ and a partition $pi=(P_1,P_2,ldots,P_m)$ of $1,2,ldots,n$, the multiple Kneser hypergraph ${mKG}^r(pi;vecs;k)$ is a hypergraph with the vertex set ${\displaystyle }$V=left{A: Asubseteq P_1cup P_2cupcdots cup P_m, |A|=k, forall 1leq ileq m; |Acap P_i|leq s_i ight}${\displaystyle }$ whose edge set is consist of any $r$ pairwise disjoint vertices. We determine the chromatic number of multiple Kneser hypergraphs provided that $r=2$ or for any $1leqileqm$, we have $|P_i|leq2s_i$. A subset $Ssubseteq[n]$ is almost $s$-stable if for any two distinct elements $i,jinS$, we have $|i-j|geqs$. The almost $s$-stable Kneser hypergraph ${mKG}^r(n,k{)}_{s-stab}^{sim}$ has all $s$-stable subsets of $[n]$ as the vertex set and every $r$-tuple of pairwise disjoint vertices forms an edge. Meunier [The chromatic number of almost stable Kneser hypergraphs. J. Combin. Theory Ser. A, 118(6):1820--1828, 2011] showed for any positive integer $r$, $chi({mKG}^r(n,k{)}_{2-stab}^{sim})=leftlceiln-r(k-1)overr-1ightceil$. We extend this result to a large family of Schrijver hypergraphs. Finally, we present a colorful-type result which confirms the existence of a completely multicolored complete bipartite graph in any coloring of a graph.

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

Recommendations

• Chromatic number of random Kneser hypergraphs
• Colorful subhypergraphs in Kneser hypergraphs
• On the chromatic number of almost stable general Kneser hypergraphs
• Chromatic numbers of stable Kneser hypergraphs via topological Tverberg-type theorems
• On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs

zbMATH Keywords

chromatic numberKneser hypergraphs\(Z_p\)-Tucker lemmaTucker-Ky Fan's lemma

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• 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
• The Chromatic Number of Kneser Hypergraphs
• Title not available (Why is that?)
• Coloring graphs with locally few colors
• 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
• Circular chromatic number: A survey
• Circular coloring and Mycielski construction
• Circular chromatic number of Kneser graphs
• Generalized Kneser coloring theorems with combinatorial proofs
• A short proof for Chen's alternative Kneser coloring lemma
• A combinatorical proof of Kneser's conjecture
• A new coloring theorem of Kneser graphs
• A generalization of Tucker's combinatorial lemma with topological applications
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Multichromatic numbers, star chromatic numbers and Kneser graphs
• A topological lower bound for the circular chromatic number of Schrijver graphs
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Evenly distributed subsets of \(S^ n\) and a combinatorial application
• The chromatic number of almost stable Kneser hypergraphs
• Kneser Representations of Graphs
• Title not available (Why is that?)
• A generalization of Kneser's conjecture
• Fractional multiples of graphs and the density of vertex-transitive graphs
• Box complexes, neighborhood complexes, and the chromatic number
• Colourful theorems and indices of homomorphism complexes
• Stable Kneser hypergraphs and ideals in $\mathbb {N}$ with the Nikodým property
• The chromatic covering number of a graph
• Title not available (Why is that?)

Cited In (26)

• On the chromatic number of generalized Kneser hypergraphs
• Topological Bounds for Graph Representations over Any Field
• Lower bounds for the chromatic number of certain Kneser-type hypergraphs
• Coloring properties of categorical product of general Kneser hypergraphs
• Hedetniemi's conjecture for Kneser hypergraphs
• On the number of star‐shaped classes in optimal colorings of Kneser graphs
• Colorful subhypergraphs in Kneser hypergraphs
• On some topological and combinatorial lower bounds on the chromatic number of Kneser type hypergraphs
• Intersection patterns of finite sets and of convex sets
• Chromatic number of random Kneser hypergraphs
• On chromatic number and minimum cut
• Chromatic number via Turán number
• On the Chromatic Number of Matching Kneser Graphs
• Strengthening topological colorful results for graphs
• On the generalized Erdős-Kneser conjecture: proofs and reductions
• On the chromatic number of a subgraph of the Kneser graph
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• On the chromatic number of Kneser hypergraphs
• Dold's theorem from viewpoint of strong compatibility graphs
• A new lower bound for the chromatic number of general Kneser hypergraphs
• Circular chromatic number of induced subgraphs of Kneser graphs
• Colorful subhypergraphs in uniform hypergraphs
• New construction of graphs with high chromatic number and small clique number
• Altermatic number of categorical product of graphs
• Concerning a conjecture on matching Kneser graphs

This page was built for publication: On the chromatic number of general Kneser hypergraphs

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