On optimal \(k\)-fold colorings of webs and antiwebs (Q1759864): Difference between revisions

A \(k\)-fold \(x\)-colouring of a graph is an assignment of (at least) \(k\) distinct colours from the set \(\{1,2,\dots,x\}\) to each vertex such that any two adjacent vertices are assigned disjoint sets of colours. The smallest number \(x\) such that a graph \(G\) admits a \(k\)-fold \(x\)-colouring is the \(k\)th chromatic number of \(G\), denoted by \(\chi_k(G)\). The paper deals with graphs that are called webs and antiwebs, where a web is a graph \(W^n_p\) with vertex set \(\{v_0,v_1,\dots,v_n\}\), \(p\geq 1\), \(n\geq 2p\) and edge set \(\{v_i v_j:p\leq |i-j|\leq n-p\}\) and an antiweb is its complement. The authors determine exact values of the studied invariant for webs and antiwebs. The obtained results provide a generalization of the known results for odd cycles and imply necessary and sufficient conditions under which \(\chi_k (G)\) attains its lower and upper bounds based on clique and integer and fractional chromatic numbers. Moreover, the authors introduce the concept of \(\chi_k\)@-critical graphs.