Abstract
In this work, we present a generalization of Gale's lemma. Using this generalization, we introduce two sharp combinatorial lower bounds for coind (B0(G)) + 1 andcoind(B(G)) + 2, the two classic topological lower boundsfor the chromatic number of a graph G.
Original language | English |
---|---|
Journal | Journal of Graph Theory |
Volume | 88 |
Issue number | 2 |
Pages (from-to) | 337-346 |
ISSN | 0364-9024 |
DOIs | |
Publication status | Published - 2017 |
Keywords
- Box complex
- Chromatic number of graphs
- Gale's lemma