\(T\)-colorings of graphs (Q1197028): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3322121 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pair Labellings with Given Distance / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4731201 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Homomorphisms of graphs into odd cycles / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: List \(T\)-colorings of graphs / rank | |||
Normal rank |
Revision as of 15:10, 16 May 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