Colorful subgraphs in Kneser-like graphs

2005/12/01 by Simonyi, Gábor, Tardos, Gábor · 2 citations
#05C15 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0512019

Abstract

Combining Ky Fan's theorem with ideas of Greene and Matousek we prove a generalization of Dol'nikov's theorem. Using another variant of the Borsuk-Ulam theorem due to Bacon and Tucker, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F. E. Su.

Cited by

• Covering and labeling generalizations of the Borsuk-Ulam theorem
• Alternating odd cycles and orientations of Kneser-like graphs

Related

• Colorful hypergraphs in Kneser hypergraphs
• Local chromatic number, Ky Fan's theorem, and circular colorings
• Colorful Subhypergraphs in Uniform Hypergraphs
• Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture
• A note on b-coloring of Kneser graphs