Coloración T

Dos coloraciones T de un gráfico para T = {0, 1, 4}

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)|\notin 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]

Relación con el número cromático

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)|\notin T.}$ ${\displaystyle \chi _{T}(G)\leq k=\chi (G).}$ ${\displaystyle \chi _{T}(G)=\chi (G).}$

yo-durar

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, ${\displaystyle \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.}$

Véase también

• Coloración de gráficos

Referencias

1. Chartrand, Gary ; Zhang, Ping (2009). "14. Coloraciones, distancia y dominación". Teoría de grafos cromáticos . CRC Press. págs. 397–402.
2. WK Hale, Asignación de frecuencia: teoría y aplicaciones. Proc. IEEE 68 (1980) 1497–1514.
3. MB Cozzens y FS Roberts, Coloraciones T de gráficos y el problema de asignación de canales. Congr. Numer. 35 (1982) 191–208.
4. Chartrand, Gary ; Zhang, Ping (2009). "14. Coloraciones, distancia y dominación". Teoría de grafos cromáticos . CRC Press. pág. 399.
5. MB Cozzens y FS Roberts, T-coloraciones de gráficos y el problema de asignación de canales. Congr. Numer. 35 (1982) 191–208.