On chromatic number and minimum cut

For a graph G, the tree Kneser graph KG(G,T t ) has all tree subgraphs of G with t vertices as vertex set and two vertices are adjacent if their corresponding trees are edge-disjoint. Also, the r-th cut number of G is the minimum number of edges between the parts of a partition of the vertex set of G into two parts such that each part has size at least r.

In this paper, we investigate the chromatic number of tree Kneser graphs. Roughly speaking, we prove that for any nonnegative integer function t=t(n), where n−t=o(n), if n is sufficiently large, then for any dense graph G with n vertices, the chromatic number of the tree Kneser graph KG(G,T t ) is equal to the (n−t+1)-th cut number of G.

In particular, as a consequence of this result, if n is large enough, then for any dense graph G with n vertices, the chromatic number of the tree Kneser graph KG(G,T n ) is equal to the minimum cut (minimum degree) of G. This result can be somehow considered a reminiscent of the Nash-Williams disjoint trees theorem.

The proof is based on a lower bound for the chromatic number of graphs found by the present authors Alishahi and Hajiabolhassan (2015) [1] which is inspired by Tucker's lemma, an equivalent combinatorial version of the Borsuk-Ulam theorem. Finally, motivated by the aforementioned results, we close the paper by a discussion on the complexity of determining the r-th cut number of graphs.