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.

05C15 Coloring of graphs and hypergraphs