Toric ideal of matching polytopes and edge colorings
arXiv:2501.19209 · doi:10.1112/mtk.70099
Abstract
In the present paper, 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 . 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. Finally, we discuss the maximal degree of minimal generators of the toric ideal associated to a general graph and give a conjecture.
14 pages, 9 figures, several typos have been corrected, the grant information and References have been updated