عدد تناوبی گراف‌ها

نویسندگان
1 دانشگاه شهید بهشتی، دانشکدۀ علوم ریاضیدانشگاه صنعتی دانمارک، دانشکدۀ ریاضی کاربردی و علوم کامپیوتر، کپنهاگ، دانمارک
2 دانشگاه صنعتی شاهرود، دانشکده علوم ریاضی
چکیده
در سال 2015، حاجی­ابوالحسن و علیشاهی عددهای تناوبی گراف‌ها را به‌عنوان یک کران پایین برای عدد رنگی گراف‌ها معرفی کردند. اثبات ارائه شده به‌وسیلۀ آن‌ها مبتنی برلم تاکر (معادل ترکیبیاتی قضیه بورسوک-اولام) است که یک نتیجه در ترکیبیات توپولوژیکی است. در این مقاله یک اثبات کاملاً ترکیبیاتی برای این قضیه از علیشاهی و حاجی­ابوالحسن ارائه می‌شود.
کلیدواژه‌ها

عنوان مقاله English

On the Altermatic Number of Graphs

نویسندگان English

Hossein Hajiabolhassan 1
Meysam Alishahi 2
چکیده English

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

کلیدواژه‌ها English

Kneser graphs
Chromatic number of graphs
Alternation number of graphs
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. ##