On optimal k-fold colorings of webs and antiwebs

• Published in: Discrete Applied Mathematics 2013-01, Vol.161 (1-2), p.60-70
• Main Authors: Campêlo, Manoel, Corrêa, Ricardo C., Moura, Phablo F.S., Santos, Marcio C.
• Format: Article
• Language: English
• Subjects: ([formula omitted]-fold) graph coloring; (fractional) chromatic number; Clique and stable set numbers; Web and antiweb
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2012.07.013

A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1,2,…,x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number x such that G admits a k-fold x-coloring is the k-th chromatic number of G, denoted by χk(G). We determine the exact value of this parameter when G 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) 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-critical graphs. We identify the webs and antiwebs having this property, for every integer k≥1.