A topological lower bound for the chromatic number of a special family of graphs

Research output: Journal PublicationArticlepeer-review

1 Citation (Scopus)

Abstract

For studying topological obstructions to graph colorings, Hom-complexes were introduced by Lovász. A graph T is called a test graph if for every graph H, the k-connectedness of |Hom(T,H)| implies χ(H)≥k+1+χ(T). The proof of the famous Kneser conjecture is based on the fact that K2, the complete graph on 2 vertices, is a test graph. This result was extended to all complete graphs by Babson and Kozlov. Their proof is based on generalized nerve lemma and discrete Morse theory. In this paper, we propose a new topological lower bound for the chromatic number of a special family of graphs. As an application of this bound, we give a new proof of the well-known fact that complete graphs are test graphs.

Original languageEnglish
Pages (from-to)508-512
Number of pages5
JournalDiscrete Mathematics
Volume341
Issue number2
DOIs
Publication statusPublished - Feb 2018
Externally publishedYes

Keywords

  • Graph coloring
  • Graph homomorphism
  • Hom complex
  • Test graph

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'A topological lower bound for the chromatic number of a special family of graphs'. Together they form a unique fingerprint.

Cite this