Toric ideals arising from matching polytopes and graph colorings

This talk is based on joint work with Ryo Motomura, Hidefumi Ohsugi, and Akiyoshi Tsuchiya. A matching of a graph $G$ is a set of pairwise non-adjacent edges of $G$. We investigate the maximal degree of minimal generators of the toric ideal of the matching polytope of a graph. It is known that the toric ideal associated to a bipartite graph is generated by binomials of degree at most $3$. We show that this fact is equivalent to a result in the theory of edge colorings of bipartite multigraphs.

Moreover, a characterization of bipartite graphs whose toric ideals are generated by quadratic binomials is given.