Tropical matchings in vertex-colored graphs

A subgraph of a vertex-colored graph is said to be tropical whenever it contains all colors of the original graph. In this work we study the problem of finding, if any, maximum tropical matchings in vertex-colored graphs. We show that this problem is polynomial with complexity max⁡{O(cm),O(nm)}. We also provide a polynomial algorithm of time O(nmn) for finding, if any, a minimum tropical matching in vertex-colored graphs.