Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.18487 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908503560421376 |
|---|---|
| author | Almási, Nóra Simonyi, Gábor |
| author_facet | Almási, Nóra Simonyi, Gábor |
| contents | We call an oriented odd cycle alternating if it has exactly one vertex whose in-degree and out-degree are both positive. In this paper, we investigate whether certain graphs admit an orientation that avoids alternating odd cycles as subgraphs, or one in which all their shortest odd cycles become alternating. Our focus is on topologically $χ$-chromatic graphs, that is, graphs for which the topological method yields a sharp lower bound on the chromatic number. We present results for several graph families, including Kneser graphs, Schrijver graphs, and generalized Mycielski graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18487 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Alternating odd cycles and orientations of Kneser-like graphs Almási, Nóra Simonyi, Gábor Combinatorics We call an oriented odd cycle alternating if it has exactly one vertex whose in-degree and out-degree are both positive. In this paper, we investigate whether certain graphs admit an orientation that avoids alternating odd cycles as subgraphs, or one in which all their shortest odd cycles become alternating. Our focus is on topologically $χ$-chromatic graphs, that is, graphs for which the topological method yields a sharp lower bound on the chromatic number. We present results for several graph families, including Kneser graphs, Schrijver graphs, and generalized Mycielski graphs. |
| title | Alternating odd cycles and orientations of Kneser-like graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.18487 |