\([r,s,t]\)-colorings of graphs
type: Item
instance of: scholarly article
title: \([r,s,t]\)-colorings of graphs
zbMATH Open document ID: 1115.05033
author: Arnfried Kemnitz
author: Massimiliano Marangio
published in: Discrete Mathematics
publication date: 2007-02-13T00:00:00Z
review text: 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.
reviewed by: L. Traldi
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5124986
zbMATH Keywords: chromatic index
zbMATH Keywords: total chromatic number
MaRDI profile type: Publication
full work available at URL: j.disc.2006.06.030
OpenAlex ID: W2066602031
cites work: On the total coloring of planar graphs.
cites work: Q5782525
cites work: The total chromatic number of graphs having large maximum degree
cites work: 25 pretty graph colouring problems
cites work: The total chromatic number of any multigraph with maximum degree five is at most seven
cites work: A bound on the total chromatic number
cites work: On total 9-coloring planar graphs of maximum degree seven
cites work: Total colourings of graphs
DOI: 10.1016/J.DISC.2006.06.030
Recommended article: COMPOUND-COMMUTING ADDITIVE MAPS ON MATRIX SPACES
Recommended article: A note on \([r, s, c, t]\)-colorings of graphs
Recommended article: \([r,s,t]\)-coloring of \(K_{n,n}\)
Recommended article: \(T\)-colorings of graphs
Recommended article: \([r,s,t]\)-coloring of trees and bipartite graphs
Recommended article: \([r,s,t]\)-colorings of graph products
Recommended article: Q3515428
Recommended article: Q5284044
Recommended article: Q3598057
Recommended article: \((\mathcal{P},\mathcal{Q})\)-total \((r,s)\)-colorings of graphs
description: scientific article; zbMATH DE number 5124986