A combinatorial proof for the circular chromatic number of Kneser graphs

• Alon N, Frankl P, Lovász LL (1986) The chromatic number of Kneser hypergraphs. Trans Am Math Soc 298:359–370

  Article  MathSciNet  MATH  Google Scholar 

• Bárány I (1978) A short of Kneser’s conjecture. J Combin Theory A 25:325–326

  Article  MATH  Google Scholar 

• Chang GJ, Liu DD-F, Zhu X (2013) A short proof for Chen’s Alternative Kneser Coloring Lemma. J Combin Theory A 120:159–163

  Article  MathSciNet  MATH  Google Scholar 

• Chen P-A (2011) A new coloring theorem of Kneser graphs. J Combin Theory A 118(3):1062–1071

  Article  MathSciNet  MATH  Google Scholar 

• Fan K (1952) A generalization of Tucker’s combinatorial lemma with topological applications. Ann Math 2(56):431–437

  Article  MATH  Google Scholar 

• Freund RM, Todd MJ (1981) A constructive proof of Tucker’s combinatorial lemma. J Combin Theory A 30:321–325

  Article  MathSciNet  MATH  Google Scholar 

• Greene J (2002) A new short proof of Kneser’s conjecture. Am Math Monthly 109:918–920

  Article  MathSciNet  MATH  Google Scholar 

• Hajiabolhassan H, Zhu X (2003) Circular chromatic number of Kneser graphs. J Combin Theory B 88(2):299–303

  Article  MathSciNet  MATH  Google Scholar 

• Hajiabolhassan H, Taherkhani A (2010) Graph powers and graph homomorphisms. Electron J Combin 17(1):R17

  MathSciNet  MATH  Google Scholar 

• Johnson A, Holroyd FC, Stahl S (1997) Multichromatic numbers, star chromatic numbers and Kneser graphs. J Graph Theory 26(3):137–145

  Article  MathSciNet  MATH  Google Scholar 

• Kneser M (1955) Aufgabe 300. Jber Deutsch Math Verein 58:27

  Google Scholar 

• Kriz I (1992) Equivalent cohomology and lower bounds for chromatic numbers. Trans Am Math Soc 333:567–577

  Article  MathSciNet  MATH  Google Scholar 

• Kriz I (2000) A corretion to “Equivalent cohomology and lower bounds for chromatic numbers. Trans Am Math Soc 352:1951–1952

  Article  MathSciNet  Google Scholar 

• Lih K-W, Liu DD-F (2002) Circular chromatic numbers of some reduced Kneser graphs. J Graph Theory 41:62–68

  Article  MathSciNet  MATH  Google Scholar 

• Lovász L (1978) Kneser’s conjecture, chromatic number, and homotopy. J Combin Theory A 25(3):319–324

  Article  MATH  Google Scholar 

• Matoušek J (2003) Using the Borsuk–Ulam theorem: lectures on topological methods in combinatorics and geometry. Springer, Berlin

  MATH  Google Scholar 

• Matoušek J (2004) A combinatorial proof of Kneser’s conjecture. Combinatorica 24:163–170

  Article  MathSciNet  MATH  Google Scholar 

• Meunier F (2005) A topological lower bound for the circular chromatic number of Schrijver graphs. J Graph Theory 49(4):257–261

  Article  MathSciNet  MATH  Google Scholar 

• Prescott T, Su F (2005) A constructive proof of Ky Fan’s generalization of Tucker’s lemma. J Combin Theory A 111:257–265

  Article  MathSciNet  MATH  Google Scholar 

• Sarkaria KS (1990) A generalized Kneser conjecture. J Combin Theory B 49:236–240

  Article  MathSciNet  MATH  Google Scholar 

• Schrijver A (1978) Vertex-critical subgraphs of Kneser graphs. Nieuw Arch Wiskd III 26:454–461

  MathSciNet  MATH  Google Scholar 

• Simonyi G, Tardos G (2006) Local chromatic number, Ky Fan’s theorem and circular colorings. Combinatorica 26(5):587–626

  Article  MathSciNet  MATH  Google Scholar 

• Tucker AW (1946) Some topological properties of disk and sphere. In: Proceedings of the first Canadian Mathematical Congress, Montreal. University of Toronto Press, Toronto, pp 285–309

• Zhu X (2001) Circular chromatic number: a survey. Discrete Math 229(1–3):371–410

  Article  MathSciNet  MATH  Google Scholar 

• Zhu X (2006) Recent developments in circular colouring of graphs. Topics in discrete mathematics. Algorithms and combinatorics, vol 26. Springer, Berlin, pp 497–550

• Zhu X (2012) Circular coloring and flow. Lecture note

• Ziegler G (2002) Generalized Kneser coloring theorems with combinatorial proofs. Invent Math 147:671–691

  Article  MathSciNet  MATH  Google Scholar 

Download references