\([r,s,t]\)-colorings of graphs (Q864161): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1016/j.disc.2006.06.030 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.DISC.2006.06.030 / rank
 
Normal rank

Latest revision as of 06:00, 10 December 2024

scientific article
Language Label Description Also known as
English
\([r,s,t]\)-colorings of graphs
scientific article

    Statements

    \([r,s,t]\)-colorings of graphs (English)
    0 references
    0 references
    0 references
    13 February 2007
    0 references
    The authors introduce \([r,s,t]\)-colorings of graphs, which generalize vertex colorings, edge colorings, and total colorings. Given non-negative integers \( k\), \(r\), \(s\) and \(t\), an \([r,s,t]\)-coloring of a graph \(G=(V(G),E(G))\) is a mapping \(c:V(G)\cup E(G)\rightarrow \{0,\dots,k-1\}\) such that \(\left| c(v_{i})-c(v_{j})\right| \geq r\) whenever the vertices \(v_{i}\) and \(v_{j} \) are adjacent, \(\left| c(e_{i})-c(e_{j})\right| \geq s\) whenever the edges \(e_{i}\) and \(e_{j}\) are adjacent, and \(\left| c(v_{i})-c(e_{j})\right| \geq t\) whenever the vertex \(v_{i}\) is incident on the edge \(e_{j}\). The \([r,s,t]\)-chromatic number \(\chi _{r,s,t}(G)\) is the least \(k\) such that \(G\) admits an \([r,s,t]\)-coloring with \(k\) colors. The paper includes several general results about \([r,s,t]\)-colorings; for instance \(\chi _{ar,as,at}(G)=1+a(\chi _{r,s,t}(G)-1)\) and \(r\chi (G)-r+s\chi ^{\prime }(G)-s+t+1\geq \chi _{r,s,t}(G)\geq 1+\max \{r\chi (G)-r,s\chi ^{\prime }(G)-s,t\}\). In addition, the values of \(\chi _{r,s,t}(G) \) with \(\min \{r,s,t\}\leq 1\) are discussed in detail.
    0 references
    chromatic index
    0 references
    total chromatic number
    0 references

    Identifiers