Path multicoloring in spider graphs with even color multiplicity

We give an exact polynomial-time algorithm for the problem of coloring a collection of paths defined on a spider graph using a minimum number of colors (Min-PMC), while respecting a given even maximum admissible color multiplicity on each edge. This complements a previous result on the complexity of Min-PMC in spider graphs, where it was shown that, for every odd k, the problem is NP-hard in spiders with admissible color multiplicity k on each edge. We also obtain an exact polynomial-time algorithm for maximizing the number of colored paths with a given number of colors (Max-PMC) in spider graphs with even admissible color multiplicity on each edge.