On optimal kk-fold colorings of webs and antiwebs

A kk-fold xx-coloring of a graph is an assignment of (at least) kk distinct colors from the set {1,2,…,x}{1,2,…,x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number xx such that GG admits a kk-fold xx-coloring is the kk-th chromatic number of GG, denoted by χk(G)χk(G). We determine the exact value of this parameter when GG is a web or an antiweb. Our results generalize the known corresponding results for odd cycles and imply necessary and sufficient conditions under which χk(G)χk(G) attains its lower and upper bounds based on clique and integer and fractional chromatic numbers. Additionally, we extend the concept of χχ-critical graphs to χkχk-critical graphs. We identify the webs and antiwebs having this property, for every integer k≥1k≥1.