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

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
Normalize DOI.
 
(4 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.dam.2012.07.013 / rank
Normal rank
 
Property / author
 
Property / author: Manoel B. Campêlo / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Gabriel Semanisin / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1562041694 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1108.5757 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.DAM.2012.07.013 / rank
 
Normal rank

Latest revision as of 08:58, 11 December 2024

scientific article
Language Label Description Also known as
English
On optimal \(k\)-fold colorings of webs and antiwebs
scientific article

    Statements

    On optimal \(k\)-fold colorings of webs and antiwebs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    22 November 2012
    0 references
    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.
    0 references
    \(k\)-fold graph coloring
    0 references
    fractional chromatic number
    0 references
    clique number
    0 references
    stable set number
    0 references
    web
    0 references
    antiweb
    0 references

    Identifiers