Coloración T

En teoría de grafos , una coloración T de un grafo , dado el conjunto T de enteros no negativos que contienen 0, es una función que asigna cada vértice a un entero positivo ( color ) tal que si u y w son adyacentes entonces . ^[1] En palabras simples, el valor absoluto de la diferencia entre dos colores de vértices adyacentes no debe pertenecer al conjunto fijo T . El concepto fue introducido por William K. Hale. ^[2] Si T = {0} se reduce a la coloración de vértices común. ${\displaystyle G=(V,E)}$ ${\displaystyle c:V(G)\to \mathbb {N}}$${\displaystyle |c(u)-c(w)|\no en T}$

El número T -cromático , es el número mínimo de colores que se pueden utilizar en una T - coloración de G.${\displaystyle \chi_{T}(G),}$

La coloración complementaria de T -coloración c , denotada se define para cada vértice v de G por ${\displaystyle {\overline {c}}}$

${\displaystyle {\overline {c}}(v)=s+1-c(v)}$

donde s es el color más grande asignado a un vértice de G por la función c . ^[1]

Proposición. . ^[3]${\displaystyle \chi_{T}(G)=\chi(G)}$

Demostración. Toda coloración T de G es también una coloración de vértice de G , por lo que Supóngase que y Dada una función de coloración k de vértice común que utiliza los colores Definimos como ${\displaystyle \chi _{T}(G)\geq \chi (G).}$${\displaystyle \chi(G)=k}$${\displaystyle r=\max(T).}$${\displaystyle c:V(G)\to \mathbb {N}}$${\displaystyle \{1,\ldots ,k\}.}$${\displaystyle d:V(G)\to \mathbb {N}}$

${\displaystyle d(v)=(r+1)c(v)}$

Para cada dos vértices adyacentes u y w de G ,

${\displaystyle |d(u)-d(w)|=|(r+1)c(u)-(r+1)c(w)|=(r+1)|c(u)-c(w)|\geq r+1}$

Por lo tanto, d es una coloración T de G. Dado que d utiliza k colores, en consecuencia,${\displaystyle |d(u)-d(w)|\no en T.}$${\displaystyle \chi_{T}(G)\leq k=\chi(G).}$${\displaystyle \chi_{T}(G)=\chi(G).}$

El lapso de una T -coloración c de G se define como

${\displaystyle sp_{T}(c)=\max _{u,w\in V(G)}|c(u)-c(w)|.}$

El T -span se define como:

${\displaystyle sp_{T}(G)=\min _{c}sp_{T}(c).}$^[4]

A continuación se dan algunos límites del intervalo T :

• Para cada grafo k -cromático G con camarilla de tamaño y cada conjunto finito T de números enteros no negativos que contienen 0,${\estilo de visualización \omega}$${\displaystyle sp_{T}(K_{\omega })\leq sp_{T}(G)\leq sp_{T}(K_{k}).}$

• Para cada grafo G y cada conjunto finito T de números enteros no negativos que contienen 0 cuyo elemento más grande es r , ^[5]${\displaystyle sp_{T}(G)\leq (\chi (G)-1)(r+1).}$

• Para cada grafo G y cada conjunto finito T de números enteros no negativos que contienen 0 cuya cardinalidad es t , ^[5]${\displaystyle sp_{T}(G)\leq (\chi (G)-1)t.}$

• Coloración de gráficos