An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of G-v to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of k.

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.

Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph G encodes the combinatorics of search trees on G, defined recursively by a root r together with search trees on each of the connected components of G − r. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. It is known that the diameter of the associahedra of paths of length n, the classical associahedra, is 2n - 6 for a large enough n. We give a tight bound of Θ(m) on the diameter of trivially perfect graph associahedra on m edges. We consider the maximum diameter of associahedra of graphs on n vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. Finally, we prove that the maximum diameter of associahedra of graphs of pathwidth two is Θ(n log n).

A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. We consider the direct product of complete graphs Km × Kn. It is known that if at least one of the numbers m or n is even, then Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1, except when m = n = 2. We prove that the graph Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1 when both m and n are odd numbers, ensuring in this way that all graphs Km × Kn have total chromatic number equal to ∆ (Km × Kn) + 1, except when m = n = 2.

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.

The circular arc coloring problem consists of finding a minimum coloring of a circular arc family F such that no two intersecting arcs share a color. Let l be the minimum number of circular arcs in F that are needed to cover the circle. Tucker shows in [SIAM J. Appl. Math., 29 (1975), pp. 493--502], that if $l \geq 4$, then $\lfloor \frac{3}{2}L \rfloor$ colors suffice to color F, where L denotes the load of F. We extend Tucker's result by showing that if $l \geq 5$, then $\lceil (\frac{l-1}{l-2} ) L \rceil$ colors suffice to color F, and this upper bound is tight.