A note on toric ideals of graphs and Knutson-Miller-Yong Decompositions

We use a Gröbner basis technique first introduced by Knutson, Miller and Yong to study the interplay between properties of a graph [Formula: see text] and algebraic properties of the toric ideal that it defines. We first recover a well-known height formula for the toric ideal of a graph [Formula: see text] and demonstrate an algebraic property that can detect when a graph deletion is bipartite. We also bound the chromatic number [Formula: see text] using information about an initial ideal of [Formula: see text].