Número cromático

El número cromático del grafo G es el mínimo número de colores en el que es posible colorear [1] los vértices del grafo G de manera que los extremos de cualquier arista tengan colores diferentes. Usualmente denotado χ( G ).

Definición

El número cromático de un gráfico es el número mínimo tal que el conjunto de vértices del gráfico se puede dividir en clases disjuntas : $k$ $V$ $k$ $C_{1},C_{2},\ldots,C_{k}$

V=\bigcup _{i}^{{}}C_{i};\ C_{i}\cap C_{j}=\varnada,

tal que los vértices de cada clase son independientes , es decir, ninguna arista del gráfico conecta vértices de la misma clase.

Definiciones relacionadas

Un gráfico coloreable K es un gráfico cuyo número cromático no excede . Es decir, sus vértices se pueden colorear con nada más que colores de tal manera que cada arista termine en un color diferente. $k$ $k$
Un gráfico K-cromático es un gráfico cuyo número cromático es . Es decir, los vértices del gráfico se pueden colorear con colores para que cualquier borde termine en diferentes colores, pero ya no es posible colorear con colores de esta manera. $k$ $k$ $K-1$

Coloración de bordes

La clase cromática de un grafo G es el número mínimo de colores en los que se pueden colorear las aristas del grafo G para que las aristas adyacentes tengan colores diferentes. Denotado χ'( G ). El problema de colorear los bordes de un gráfico cúbico plano arbitrario sin puentes con tres colores es equivalente al famoso Problema de los cuatro colores . La coloración de los bordes define una factorización en 1 de un gráfico.

Polinomio cromático

Si consideramos el número de colores diferentes de un gráfico etiquetado como una función del número de colores disponibles t , resulta que esta función siempre será un polinomio en t . Este hecho fue descubierto por Birkhoff y Lewis [2] al intentar probar el problema de los cuatro colores .

Polinomios cromáticos de algunos gráficos

Triángulo $K_{3}$	$t(t-1)(t-2)$
Gráfico completo $K_n$	$t(t-1)(t-2)...(t-(n-1))$
árbol con vértices $norte$	$t(t-1)^{{n-1}}$
Ciclo $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Conde de Petersen	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t- 352)$

Encontrar el polinomio cromático de un gráfico arbitrario

Para un gráfico de vértice, el polinomio cromático es $t$

|V(G)|=1\Flecha derecha P(G,t)=t.

El polinomio cromático de un gráfico es igual al producto de los polinomios cromáticos de sus componentes

G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t ).

También hay una relación recursiva: el teorema de Zykov [3] , la llamada fórmula de eliminación y contracción

P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),

donde y son vértices adyacentes, es un gráfico obtenido a partir de un gráfico quitando una arista , y es un gráfico obtenido a partir de un gráfico contrayendo una arista a un punto. Puedes usar la fórmula equivalente $tu$ $v$ $Jefe)$ $GRAMO$ $(tú, v),$ $Jefe)$ $GRAMO$ $(u,v)$

P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),

donde y son vértices no adyacentes, y es el grafo obtenido del grafo sumando una arista $tu$ $v$ $G+(u,v)$ $GRAMO$ $(u, v).$

Propiedades del polinomio cromático

Para todos los enteros positivos $t$

P(G,t)\geq 0.

El número cromático es el entero positivo más pequeño para el cual $\ chi (G)$ $t$

P(G,t)>0.

El grado de un polinomio cromático es igual al número de vértices:

\grado P(G,t)=|V(G)|

Generalizaciones

Además, el número cromático se puede considerar para otros objetos, como los espacios métricos . Así, el número cromático de un plano es el número mínimo de colores χ para el cual existe tal coloración de todos los puntos del plano en uno de los colores que no hay dos puntos del mismo color a una distancia de exactamente 1 entre sí. otro. Lo mismo es cierto para cualquier dimensión del espacio. Está elementalmente probado que para el avión , sin embargo, no fue posible avanzar más durante mucho tiempo. El 8 de abril de 2018, el matemático británico Aubrey de Grey demostró que [4] [5] . Este problema se llama el problema de Nelson-Erdős-Hadwiger . $4\leqslant\chi\leqslant 7$ ${\ estilo de visualización \ chi> 4}$

Importancia para la teoría de grafos

Muchos problemas profundos de la teoría de grafos se formulan fácilmente en términos de coloración. El más famoso de estos problemas, el problema de los cuatro colores , ya se ha resuelto, pero están surgiendo otros nuevos, como una generalización del problema de los cuatro colores, la conjetura de Hadwiger .

Véase también

Notas

↑ Dibujo para colorear
↑ Birkhoff, GD y Lewis, DC "Polinomios cromáticos". Trans. amer Matemáticas. soc. 60, 355-451, 1946.
↑ Este dominio está estacionado por Timeweb
↑ de Grey, Aubrey DNJ (2018-04-08), El número cromático del avión es al menos 5
↑ Vladímir Korolev. Los matemáticos carecían de cuatro colores para colorear el plano . nplus1.ru. Fecha de acceso: 11 de abril de 2018. (indefinido)

Literatura

O. mineral . Teoría de grafos. — M .: Nauka, 1986.