Coloración intensa

En teoría de grafos , una coloración fuerte , con respecto a una partición de los vértices en subconjuntos (disjuntos) de igual tamaño, es una coloración de vértices (propia) en la que cada color aparece exactamente una vez en cada parte. Un grafo es fuertemente k -coloreable si, para cada partición de los vértices en conjuntos de tamaño k , admite una coloración fuerte. Cuando el orden del grafo G no es divisible por k , añadimos vértices aislados a G suficientes para que el orden del nuevo grafo G ′ ^sea divisible por k . En ese caso, una coloración fuerte de G ′ menos los vértices aislados añadidos previamente se considera una coloración fuerte de G. ^{[ 1} ]

El número cromático fuerte sχ( G ) de un grafo G es el menor k tal que G es fuertemente k -coloreable. Un grafo es fuertemente k -cromático si tiene un número cromático fuerte k .

Algunas propiedades de sχ( G ):

1. sχ( G ) > Δ( G ).
2. sχ( GRAMO ) ≤ 3 Δ( GRAMO ) − 1. ^{[ 2 ]}
3. Asintóticamente, sχ( G ) ≤ 11 Δ( G ) / 4 + o(Δ( G )). ^{[ 3 ]}

Aquí, Δ( G ) es el grado máximo .

El número cromático fuerte fue introducido independientemente por Alon (1988) ^{[ 4 ] [ 5 ]} y Fellows (1990). ^{[ 6 ]}

Dado un grafo y una partición de sus vértices, una transversal independiente es un conjunto U de vértices no adyacentes tal que cada parte contiene exactamente un vértice de U. Una coloración fuerte es equivalente a una partición de los vértices en transversales independientes disjuntas (cada transversal independiente es un único "color"). Esto contrasta con la coloración de grafos , que consiste en una partición de los vértices de un grafo en un número determinado de conjuntos independientes , sin el requisito de que estos conjuntos independientes sean transversales.

Para ilustrar la diferencia entre estos conceptos, consideremos una facultad con varios departamentos, donde el decano desea formar un comité de profesores. Sin embargo, algunos profesores están en conflicto y no participarán en el mismo comité. Si las relaciones de "conflicto" se representan mediante las aristas de un grafo, entonces:

• Un comité independiente es aquel que no presenta conflictos de intereses.
• Un comité transversal independiente es un comité sin conflicto de intereses, con exactamente un miembro de cada departamento.
• La coloración de gráficos consiste en dividir a los miembros del profesorado en comités sin conflictos.
• Una distribución equilibrada consiste en dividir a los miembros del profesorado en comités sin conflictos y con exactamente un miembro de cada departamento. Por ello, este problema a veces se denomina el problema del decano feliz . ^{[ 7 ]}