# zbMATH — the first resource for mathematics

List multi-coloring problems. (English) Zbl 0995.05060
Authors’ abstract: “Let $$G= (V,E)$$ be a graph, let each vertex have a list of colors $$L(v)\subseteq \{1,\dots, k\}$$, and an integer $$\kappa(v)$$. We consider the problem of assigning $$\kappa(v)$$ distinct colors to each vertex $$v$$ such that the $$\kappa(v)$$ colors assigned to $$v$$ are chosen from $$L(v)$$ and such that sets of colors assigned to adjacent vertices are disjoint. We focus on paths and pairs of cliques joined at a cut-vertex.”
For paths, a polynomial-time decision algorithm was presented in [M. M. Cropper, J. L. Goldwasser, A. J. W. Hilton, D. G. Hoffman and P. D. Johnson, Extending the disjoint-representatives theorem of Hall, Halmos, and Vaughan to list-multicolorings of graphs, J. Graph Theory 33, No. 4, 119-219 (2000; Zbl 0944.05040)]; the article under review analyzes its time-complexity. For pairs of cliques, this article presents a polynomial-time decision algorithm.

##### MSC:
 05C15 Coloring of graphs and hypergraphs