Gráfico crítico

En teoría de grafos , un grafo crítico es un grafo no dirigido en el que todos sus subgrafos propios tienen un número cromático menor . En un grafo de este tipo, cada vértice o arista es un elemento crítico , en el sentido de que su eliminación reduciría el número de colores necesarios para la coloración del grafo dado. La reducción del número de colores no puede ser mayor que uno.

Un grafo -crítico es un grafo crítico con número cromático . Un grafo con número cromático es -crítico en cuanto al vértice si cada uno de sus vértices es un elemento crítico. Los grafos críticos son los miembros mínimos en términos de número cromático, que es una medida muy importante en la teoría de grafos. ${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización G}$${\estilo de visualización k}$${\estilo de visualización k}$

Algunas propiedades de un grafo -crítico con vértices y aristas: ${\estilo de visualización k}$${\estilo de visualización G}$${\estilo de visualización n}$${\estilo de visualización m}$

• ${\estilo de visualización G}$tiene solo un componente
• ${\estilo de visualización G}$es finito (este es el teorema de De Bruijn-Erdős ). ^[1]
• El grado mínimo obedece a la desigualdad . Es decir, cada vértice es adyacente al menos a otros. Más fuertemente, es - conexo por aristas . ^[2]${\displaystyle \delta (G)}$${\displaystyle \delta (G)\geq k-1}$${\estilo de visualización k-1}$${\estilo de visualización G}$${\estilo de visualización (k-1)}$
• Si es un grafo regular con grado , es decir, cada vértice es adyacente a exactamente otros, entonces es un grafo completo con vértices o un grafo cíclico de longitud impar . Este es el teorema de Brooks . ^[3]${\estilo de visualización G}$${\estilo de visualización k-1}$${\estilo de visualización k-1}$${\estilo de visualización G}$ $Estilo de visualización K_ {k}}$${\estilo de visualización n=k}$
• ${\displaystyle 2m\geq(k-1)n+k-3}$. ^[4]
• ${\displaystyle 2m\geq (k-1)n+\lpiso (k-3)/(k^{2}-3)\rpiso n}$. ^[5]
• Cualquiera de ellos puede descomponerse en dos gráficos críticos más pequeños, con un borde entre cada par de vértices que incluye un vértice de cada uno de los dos subgráficos, o tiene al menos vértices. ^[6] Más fuertemente, cualquiera de ellos tiene una descomposición de este tipo, o para cada vértice de hay una -coloración en la que es el único vértice de su color y cada otra clase de color tiene al menos dos vértices. ^[7]${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización 2k-1}$${\estilo de visualización G}$${\estilo de visualización v}$${\estilo de visualización G}$${\estilo de visualización k}$${\estilo de visualización v}$

El gráfico es crítico en cuanto a vértice si y solo si para cada vértice existe una coloración adecuada óptima en la que es una clase de color singleton. ${\estilo de visualización G}$${\estilo de visualización v}$${\estilo de visualización v}$

Como demostró Hajós (1961), todo grafo crítico puede formarse a partir de un grafo completo combinando la construcción de Hajós con una operación que identifica dos vértices no adyacentes. Los grafos formados de esta manera siempre requieren colores en cualquier coloración adecuada. ^[8]${\estilo de visualización k}$ $Estilo de visualización K_ {k}}$${\estilo de visualización k}$

Un grafo doblemente crítico es un grafo conexo en el que la eliminación de cualquier par de vértices adyacentes reduce el número cromático en dos. Es un problema abierto determinar si es el único grafo doblemente crítico -cromático. ^[9]$Estilo de visualización K_ {k}}$${\estilo de visualización k}$

• Gráfica de factores críticos