2025/05/05 by Henry Echeverría, Andrea Jiménez, Echeverría, Henry +9
Computer Science · Mathematics · #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2505.02812
As evidence for the Odd Hadwiger Conjecture, Simonyi and Zsbán (2010) showed that every Kneser graph G with large enough order (compared to χ(G)) contains a totally odd subdivision of Kχ(G). A recent result of Steiner (2024), shows that every Schriver graph, and thus every Kneser graph, satisfies the Odd Hadwiger Conjecture, that is, it contains Kχ(G) as an odd minor. We strengthen these results for Kneser graphs in two ways. We show that for every t≥ 8, there are t-chromatic Kneser graphs that contain arbitrarily large complete totally odd subdivisions (and thus, odd minors). We also show that every Kneser graph contains a totally odd subdivision of Kχ(G). Kneser graphs are the prime example of graphs having chromatic number equal to its topological lower bounds. Motivated by our main results, we also study totally odd immersions on graphs with this property, proving, in particular, that if the chromatic number of G is equal to any of its topological lower bounds, then G contains a totally odd immersion of K\lfloor χ(G)/2 \rfloor +1. This gives evidence for the immersion-analogue of the Odd Hadwiger Conjecture.