Colorful subhypergraphs in Kneser hypergraphs

Frédéric Meunier

doi:10.37236/3573

Colorful subhypergraphs in Kneser hypergraphs

Frédéric Meunier

Research output: Contribution to journal › Article › peer-review

Abstract

Using a Z_q-generalization of a theorem of Ky Fan, we extend to Kneser hyper-graphs 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).

Original language	English
Journal	Electronic Journal of Combinatorics
Volume	21
Issue number	1
DOIs	https://doi.org/10.37236/3573
Publication status	Published - 12 Jan 2014

Keywords

Colorful complete p-partite hypergraph
Combinatorial topology
Kneser hypergraphs
Local chromatic number

Access to Document

10.37236/3573

Cite this

@article{1d189c6211434f309f34c090edbe9fee,

title = "Colorful subhypergraphs in Kneser hypergraphs",

abstract = "Using a Zq-generalization of a theorem of Ky Fan, we extend to Kneser hyper-graphs 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).",

keywords = "Colorful complete p-partite hypergraph, Combinatorial topology, Kneser hypergraphs, Local chromatic number",

author = "Fr{\'e}d{\'e}ric Meunier",

year = "2014",

month = jan,

day = "12",

doi = "10.37236/3573",

language = "English",

volume = "21",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

number = "1",

}

TY - JOUR

T1 - Colorful subhypergraphs in Kneser hypergraphs

AU - Meunier, Frédéric

PY - 2014/1/12

Y1 - 2014/1/12

N2 - Using a Zq-generalization of a theorem of Ky Fan, we extend to Kneser hyper-graphs 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).

AB - Using a Zq-generalization of a theorem of Ky Fan, we extend to Kneser hyper-graphs 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).

KW - Colorful complete p-partite hypergraph

KW - Combinatorial topology

KW - Kneser hypergraphs

KW - Local chromatic number

UR - https://www.scopus.com/pages/publications/84892584287

U2 - 10.37236/3573

DO - 10.37236/3573

M3 - Article

AN - SCOPUS:84892584287

SN - 1077-8926

VL - 21

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

Colorful subhypergraphs in Kneser hypergraphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this