Esta escalera de Möbius es muy coloreable en 4 dimensiones. Hay 35 particiones de tamaño 4, pero solo estas 7 particiones son topológicamente distintas.
En teoría de grafos , una coloración fuerte , con respecto a una partición de los vértices en subconjuntos (disjuntos) de tamaños iguales, es una coloración de vértice (adecuada) 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 , agregamos vértices aislados a G lo suficiente para hacer 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 agregados 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 ):
sχ( G ) > Δ( G ).
sχ( GRAMO ) ≤ 3 Δ( GRAMO ) − 1. [2]
Asintóticamente, sχ( G ) ≤ 11 Δ( G ) / 4 + o(Δ( G )). [3]
El número cromático fuerte fue introducido independientemente por Alon (1988) [4] [5] y Fellows (1990). [6]
Problemas relacionados
Dado un grafo y una partición de los vértices, una transversal independiente es un conjunto U de vértices no adyacentes tales 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 es una partición de los vértices de un grafo en un número dado de conjuntos independientes , sin el requisito de que estos conjuntos independientes sean transversales.
Para ilustrar la diferencia entre estos conceptos, considere una facultad con varios departamentos, donde el decano quiere construir un comité de miembros de la facultad. Pero algunos miembros de la facultad están en conflicto y no se sentarán en el mismo comité. Si las relaciones de "conflicto" están representadas por los bordes de un gráfico, entonces:
Un conjunto independiente es un comité sin conflicto.
Una transversal independiente es un comité sin conflicto, con exactamente un miembro de cada departamento.
La coloración de un gráfico es una partición de los miembros de la facultad en comités sin conflictos.
Una coloración fuerte es una división de los miembros de la facultad en comités sin conflictos y con exactamente un miembro de cada departamento. Por eso, este problema a veces se denomina el problema del decano feliz . [7]
Referencias
^ Jensen, Tommy R. (1995). Problemas de coloración de gráficos. Toft, Bjarne. Nueva York: Wiley. ISBN 0-471-02865-7.OCLC 30353850 .
^ Haxell, PE (1 de noviembre de 2004). "Sobre el número cromático fuerte". Combinatoria, probabilidad y computación . 13 (6): 857–865. doi :10.1017/S0963548304006157. ISSN 0963-5483. S2CID 6387358.
^ Haxell, PE (2008). "Un límite mejorado para el número cromático fuerte". Revista de teoría de grafos . 58 (2): 148–158. doi :10.1002/jgt.20300. ISSN 1097-0118. S2CID 20457776.
^ Alon, N. (1988-10-01). "La arboricidad lineal de grafos". Revista israelí de matemáticas . 62 (3): 311–325. doi : 10.1007/BF02783300 . ISSN 0021-2172.
^ Alon, Noga (1992). "El número cromático fuerte de un grafo". Random Structures & Algorithms . 3 (1): 1–7. doi :10.1002/rsa.3240030102.
^ Fellows, Michael R. (1990-05-01). "Transversales de particiones de vértices en grafos". Revista SIAM de Matemáticas Discretas . 3 (2): 206–215. doi :10.1137/0403018. ISSN 0895-4801.
^ Haxell, P. (1 de noviembre de 2011). "Sobre la formación de comités". The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
