Abstract | ||
---|---|---|
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 @g"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 @g"k(G) attains its lower and upper bounds based on clique and integer and fractional chromatic numbers. Additionally, we extend the concept of @g-critical graphs to @g"k-critical graphs. We identify the webs and antiwebs having this property, for every integer k=1. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.dam.2012.07.013 | Discrete Applied Mathematics |
Keywords | Field | DocType |
corresponding result,adjacent vertex,fractional chromatic number,k-fold x-coloring,k-th chromatic number,k distinct color,disjoint set,smallest number,integer k,exact value,optimal k-fold colorings,discrete mathematics,k | Integer,Graph,Discrete mathematics,Combinatorics,Disjoint sets,Clique,Fractional coloring,Vertex (geometry),Chromatic scale,Gallai–Hasse–Roy–Vitaver theorem,Mathematics | Journal |
Volume | Issue | ISSN |
161 | 1-2 | Discrete Applied Mathematics, 161(1-2), pages 60-70, 2013 |
Citations | PageRank | References |
3 | 0.42 | 19 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manoel B. Campêlo | 1 | 151 | 19.59 |
Ricardo C. Corrêa | 2 | 207 | 18.74 |
Phablo F. S. Moura | 3 | 18 | 5.40 |
Marcio C. Santos | 4 | 17 | 2.50 |