Colorful hypergraphs in Kneser hypergraphs

2013/06/05 by Frédéric Meunier, Meunier, Frédéric
Computer Science · Mathematics · #05C65 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1306.1112

openalex publication_date 2013/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Using a Z_q-generalization of a theorem of Ky Fan, we extend to Kneser hypergraphs a theorem of Simonyi and Tardos that ensures the existence of multicolored complete bipartite graphs in any proper coloring of a Kneser graph. It allows to derive a lower bound for the local chromatic number of Kneser hypergraphs (using a natural definition of what can be the local chromatic number of a hypergraph).

Citations

• On the diameter of Kneser graphs

Related

• Colorful subgraphs in Kneser-like graphs
• Colorful Subhypergraphs in Uniform Hypergraphs
• Coloring Properties of Categorical Product of General Kneser Hypergraphs
• On some topological and combinatorial lower bounds on chromatic number of Kneser type hyper graphs
• Random Kneser graphs and hypergraphs