Colorful subhypergraphs in Kneser hypergraphs

MaRDI QIDQ405073zbMATH OpenFDO

Authors Frédéric Meunier

Publication date 4 September 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.1112, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p8

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

colorful complete \(p\)-partite hypergraphcombinatorial topologyKneser hypergraphslocal chromatic number

Mathematics Subject Classification ID

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

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).

Review text

Summary: Using a \(\mathbb{Z}_q\)-generalization of a theorem of \textit{K. Fan} [Ann. Math. (2) 56, 431--437 (1952; Zbl 0047.42004)], 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 uniform hypergraph).

Recommendations

• On the chromatic number of general Kneser hypergraphs
• Colorful subgraphs in Kneser-like graphs
• On the chromatic number of generalized Kneser hypergraphs
• Chromatic number of random Kneser hypergraphs
• Lower bounds for the chromatic number of certain Kneser-type hypergraphs

Cites work

• A combinatorical proof of Kneser's conjecture
• A generalization of Tucker's combinatorial lemma with topological applications
• A topological lower bound for the circular chromatic number of Schrijver graphs
• Colorful subgraphs in Kneser-like graphs
• Coloring graphs with locally few colors
• Combinatorial Stokes formulas via minimal resolutions
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Evenly distributed subsets of \(S^ n\) and a combinatorial application
• Generalized Kneser coloring theorems with combinatorial proofs
• scientific article; zbMATH DE number 4102053 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number, Ky Fan's theorem, and circular colorings
• n-tuple colorings and associated graphs
• On the chromatic number of general Kneser hypergraphs
• On the diameter of Kneser graphs
• The chromatic number of almost stable Kneser hypergraphs
• The Chromatic Number of Kneser Hypergraphs
• Topological lower bounds for the chromatic number: a hierarchy

Cited in

(12)

• Altermatic number of categorical product of graphs
• A new lower bound for the chromatic number of general Kneser hypergraphs
• Chromatic number via Turán number
• Strengthening topological colorful results for graphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• Colorful subgraphs in Kneser-like graphs
• scientific article; zbMATH DE number 1146221 (Why is no real title available?)
• Coloring properties of categorical product of general Kneser hypergraphs
• On the chromatic number of general Kneser hypergraphs
• Colorful subhypergraphs in uniform hypergraphs
• Hedetniemi's conjecture for Kneser hypergraphs
• Coloring hypercomplete and hyperpath graphs

This page was built for publication: Colorful subhypergraphs in Kneser hypergraphs

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