## 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 K_{2}, 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 language | English |
---|---|

Pages (from-to) | 508-512 |

Number of pages | 5 |

Journal | Discrete Mathematics |

Volume | 341 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2018 |

Externally published | Yes |

## Keywords

- Graph coloring
- Graph homomorphism
- Hom complex
- Test graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics