QA381 : A COMBINATORIAL PROOF OF KNESER’S CONJECTURE
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2016
Authors:
Mehri Seyedabolhosini [Author], Meysam Alishahi[Supervisor]
Abstarct: A Kneser gragh KG(n,k) is a gragh whose vertex set is the set of all k-subsets of {1, 2, ..., n} and two vertices are adjecent if their corresponding sets are disjoint. Kneser 1955 conjectured the chromatic number of KG(n, k) is n − 2k + 2 provided that n ≥ 2k. This conjecture received an affirmative answer by a break through of Lovasz. He used algebraic topology in his proof which is known as the begining of the field of combinatorial topology. Lovasz’s result has been generalized in several ways with different proofs. In this thesis, we discuss some of these generalization.
Keywords:
#Kneser graph #chromatic number #proper coloring #circular chromatic number #traingulation #simplicial complex Link
Keeping place: Central Library of Shahrood University
Visitor: