\(T\)-colorings of graphs (Q1197028): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(92)90603-d / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2005080911 / rank | |||
Normal rank |
Latest revision as of 11:38, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(T\)-colorings of graphs |
scientific article |
Statements
\(T\)-colorings of graphs (English)
0 references
16 January 1993
0 references
Given a finite set \(T\) of natural numbers containing 0, a \(T\)-coloring of a simple graph \(G=(V(G),E(G))\) is a function \(f\) from the vertex set \(V(G)\) to natural numbers such that \(| f(u)-f(v)|\notin T\) whenever \(\{u,v\}\in E(G)\). The span of a \(T\)-coloring is defined to be the difference between the largest and smallest color used. The \(T\)-span of \(G\), denoted by \(\text{sp}_ T(G)\), is the minimum span among all \(T\)-colorings of \(G\). A graph \(G\) is weakly perfect if the chromatic number \(\chi(G)\) is equal to the clique number \(\omega(G)\). A special graph \(G^ n_ T\) plays an important role in this paper. The vertex set of \(G^ n_ T\) is \(\{0,1,2,\ldots,n-1\}\) and \(\{u,v\}\in E(G^ n_ T)\) if and only if \(| u-v|\notin T\). The main theorem shows that, given \(T\), the following are equivalent: (i) \(\text{sp}_ T(G)=\text{sp}_ T(K_{\chi(G)})\) for all graphs \(G\), (ii) \(\text{sp}_ T(G^ n_ T)=\text{sp}_ T(K_{\chi(G^ n_ T)})\) for all \(n\), (iii) \(G^ n_ T\) is weakly perfect for all \(n\). Using these equivalences, known results about sets \(T\) which satisfy (i) are derived with shorter proofs. New families of sets \(T\) with this property are also constructed. Finally, it is established that \(\text{sp}_ T(G)=\text{sp}_ T(K_ m)=n-1\) for all graphs \(G\) with \(\chi(G)=m\) if and only if \(\omega(G^ n_ T)=\chi(G^ n_ T)=m\) and \(\chi(G_ T^{n-1})<\chi(G^ n_ T)\).
0 references
coloring
0 references
chromatic number
0 references
clique number
0 references
weakly perfect
0 references