On the Altermatic Number of Graphs

Authors
Abstract
In 2015, Alishahi and Hajiabolhassan introduced the altermatic number of graphs as a lower bound for the chromatic number of them. Their proof is based on the Tucker lemma, a combinatorial counterpart of the Borsuk-Ulam theorem, which is a well-known result in topological combinatorics. In this paper, we present a combinatorial proof for the Alishahi-Hajiabolhassan theorem. ./files/site1/files/61/4.pdf
Keywords

1. Alishahi M., Hajiabolhassan H., "On the chromatic number of general Kneser hypergraphs", Journal of Combinatorial Theory, Series B, 115 (2015) 186-209. ## 2. Alishahi M., Hajiabolhassan H., "Altermatic number of categorical products of graphs", Discrete Mathematics, 341 (2018) 1316-1324. ## 3. Alishahi M., Hajiabolhassan H., "A Generalization of Gale's lemma", Journal of Graph Theory, 88(2) (2018) 337-346. ## 4. Dol’nikov V. L., "A combinatorial inequality", Sibirsk. Mat. Zh., 29 (3) 219 (1988) 53-58. ## 5. Kneser M., "Satz über abelsche Gruppenmit Anwendungen auf die Geometrie der Zahlen", Math. Z., 61 (1955) 429-434. ## 6. Kříž I., "Equivariant cohomology and lower bounds for chromatic numbers", Trans. Amer. Math. Soc., 333(2) (1992) 567-577. ## 7. Lovász L., "Kneser's conjecture, chromatic number, and homotopy", Journal of Combinatorial Theory, Series A, 25(3) (1978) 319-324. ## 8. Matoušek J., "Using the Borsuk-Ulam theorem", Universitext. Springer-Verlag, Berlin, Lectures on topological methods in combinatorics and geometry, Written in cooperation with Anders Björner and Günter M. Ziegler (2003). ## 9. Matoušek J., "A combinatorial proof of Kneser's conjecture", Combinatorica, 24(1) (2004) 163-170. ## 10. Meunier F., "Colorful Subhypergraphs in Kneser Hypergraphs", Electronic Journal of Combinatorics, 21(1): Research Paper #P1.8 (2014) 13 (electronic). ## 11. Schrijver A., "Vertex-critical subgraphs of Kneser graphs", Nieuw Arch. Wisk. (3) 26 (3) (1978) 454-461. ##