The analogue of Hadwiger’s conjecture for the immersion order states that every graph G contains K X(G) as an immersion. Our work is motivated by a strengthening of this conjecture which asserts that every graph G contains K X(G) as a totally odd immersion. As evidence for this strengthened conjecture and inspired by a result of Steiner (2024), we show 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 [x( G)/2] +1 . Kneser graphs are canonical examples of graphs satisfying such equalities for their chromatic numbers. Simonyi and Zsban (2010) showed that every Kneser graph G with large enough order (compared to x (G) ) contains a totally odd subdivision of K X(G) , thus satisfying the motivating conjecture in a strong sense. We show that, in fact, for every t ≥ 8, there are t -chromatic Kneser graphs that contain arbitrarily large complete totally odd subdivisions.

The rotation distance between two search trees on a graph G is defined as the minimum number of rotations required to transform one tree into the other. A central problem in this context is to determine the maximum rotation distance between any pair of search trees on G , which corresponds to finding the diameter of the rotation graph R(G) , or equivalently, the combinatorial diameter of the graph associahedron of G . In this article, we establish a relationship between the structure of H ( G) and H ( G - S ) for a specific subset S of edges of G . More precisely, we show that if W is a set of true twins in G , and S consists of all edges in G with both endpoints in W , then H ( G - S) is a quotient graph of R(G) . Our main result provides a lower bound for diam( R ( G - S)) in terms of diam( R ( G )). We apply this result to determine the diameter of rotation graphs of general windmill graphs. Furthermore, we improve the known bound for the diameter of graph associahedra of balanced complete bipartite graphs.

In this article we contribute to the analysis of the spectral properties of graph associahedra, providing a lower bound for the second largest eigenvalue of the graph associahedra A(G) of G. Additionally, using equitable partitions, we analyze the spectrum of stellohedra A ( K 1 , n ) , proving the existence of an eigenvalue in the interval (n - 2, n - 1] and identifying two additional small eigenvalues.

For k ≥ 1 and n ≥ 2k, the well known Kneser graph KG(n, k) has all k-element subsets of an n-element set as vertices; two such subsets are adjacent if they are disjoint. Schrijver constructed a vertex-critical subgraph SG(n, k) of KG(n, k) with the same chromatic number. In this paper, we compute the diameter of the graph SG(2k + r,k) with r ≥ 1. We obtain that the diameter of SG(2k + r, k) is equal to 2 if r ≥ 2k - 2; 3 if k≥ - 2 ≤ r ≤ 2k - 3; k if r = 1; and for 2 ≤ r ≤ k - 3, we obtain that the diameter of SG(2k + r, k) is at most equal to k - r + 1.