T-colorear

Una coloración T de un gráfico dada por un conjunto T de enteros no negativos que contienen 0 es una función que asigna cada vértice de G a un entero positivo ( color ) tal que [1] . En términos simples, el valor absoluto de la diferencia entre dos colores de vértices adyacentes no debe pertenecer a un conjunto fijo T . El concepto fue propuesto por William K. Hale [2] . Si T = {0} , esto se reduce a la coloración de vértice normal. $G=(V,E)$ $c:V(G)\rightarrow \mathbb {N}$ $(u,w)\in E(G)\Rightarrow \left|c(u)-c(w)\right|\notin T$

La coloración complementaria de un T - coloración c , que se denota como , se define para cada vértice v de la gráfica G como , donde s es el mayor número de colores asignados al vértice de la gráfica G por la función c [1] . ${\sobrelínea {c))$
${\overline {c}}(v)=s+1-c(v)$

Número cromático T

El número T-cromático es el número de colores que se pueden usar para T -colorear el gráfico G. T -el número cromático es igual al número cromático, [3] . ${\ estilo de visualización \ chi _ {T} (G)}$ ${\ estilo de visualización \ chi _ {T} (G) = \ chi (G)}$

Prueba

Cualquier coloración T de G es también una coloración de vértice de G tal que . Supongamos que y . ${\ estilo de visualización \ chi _ {T} (G) \ geqslant \ chi (G)}$ ${\ estilo de visualización \ chi (G) = k}$ $r=máx(T)$

Dada una función de coloración k de vértices con colores 1, 2,..,k. $c:V(G)\rightarrow \mathbb {N}$

Definimos cómo $d:V(G)\rightarrow \mathbb {N}$

{\ estilo de visualización d (v) = (r + 1) c (v)}

Para cualesquiera dos vértices adyacentes u y w del grafo G

\left|d(u)-d(w)\right|=\left|(r+1)c(u)-(r+1)c(w)\right|

=(r+1)\left|c(u)-c(w)\right|\geqslant r+1

entonces _ $\left|d(u)-d(w)\right|\notin T$

Así , d es una T -coloración de G. Como d usa k colores, . ${\ estilo de visualización \ chi _ {T} (G) \ leqslant k = \ chi (G)}$

Por lo tanto, ■ ${\ estilo de visualización \ chi _ {T} (G) = \ chi (G)}$

T -span

Para un T -coloreando c de un gráfico G , c es el rango sobre todo V(G). ${\displaystyle sp_{T}(c)=\max\{|c(u)-c(w)|\))$ ${\ estilo de visualización uw \ en}$

El T -span del gráfico G es todos los colorantes c del gráfico G [4] $sp_{T}(G)$ $\min\{sp_{T}(c)\}$

Algunos límites de T-span se dan a continuación:

Para cualquier coloración k de un gráfico G con una camarilla de tamaño y cualquier conjunto finito T de enteros no negativos que contengan 0, . $\omega$ $sp_{T}(K_{\omega })\leqslant sp_{T}(G)\leqslant sp_{T}(K_{k})$

Para cualquier gráfico G y cualquier conjunto finito T de números enteros no negativos que contengan 0 cuyo elemento más grande sea r , , [5] . Para cualquier gráfico G y cualquier conjunto finito T de números enteros no negativos que contengan 0 de cardinalidad t, . [5] . $sp_{T}(G)\leqslant (\chi (G)-1)(r+1)$ ${\ estilo de visualización \ chi _ {T} (G) = \ chi (G)}$
$sp_{T}(G)\leqslant (\chi (G)-1)t$ ${\ estilo de visualización \ chi _ {T} (G) = \ chi (G)}$

Notas

↑ 1 2 Chartrand, Zhang, 2009 , pág. 397–402.
↑ Hale, 1980 , pág. 1497-1514
↑ Cozzens y Roberts 1982 , pág. 191–208.
↑ Chartrand, Zhang, 2009 , pág. 399.
↑ 1 2 Cozzens y Roberts, 1982 , p. 191–208.

Literatura

Gary Chartrand, Ping Zhang. 14. Coloraciones, distancia y dominación // Teoría de grafos cromáticos. — Prensa CRC, 2009.
Hale WK Asignación de frecuencias: Teoría y aplicaciones // Proc. IEEE. - 1980. - T. 68.
Cozzens MB, Roberts FS T -coloraciones de gráficos y el problema de asignación de canales // Congr. Número .. - 1982. - Emisión. 35 .