Gráfico crítico

En teoría de grafos , un grafo crítico es un grafo no dirigido cuyos subgrafos propios tienen un número cromático menor . En dicho grafo, cada vértice o arista es un elemento crítico , en el sentido de que su eliminación reduciría la cantidad de colores necesarios para colorearlo . Cada vez que se elimina un vértice o arista (junto con sus aristas incidentes) de un grafo crítico, la reducción en la cantidad de colores necesarios para colorearlo no puede ser mayor que uno.

A${\displaystyle k}$-El gráfico crítico es un gráfico crítico con número cromático${\displaystyle k}$Un gráfico${\displaystyle G}$con número cromático${\displaystyle k}$es${\displaystyle k}$Un grafo es crítico si cada uno de sus vértices es un elemento crítico. Los grafos críticos son los elementos mínimos en términos de número cromático, una medida muy importante en la teoría de grafos.

Algunas propiedades de un${\displaystyle k}$-gráfico crítico${\displaystyle G}$con${\displaystyle n}$vértices y${\displaystyle m}$bordes:

• ${\displaystyle G}$tiene un solo componente .
• ${\displaystyle G}$es finito (este es el teorema de De Bruijn-Erdős ). ^{[ 1 ]}
• El grado mínimo${\displaystyle \delta (G)}$obedece a la desigualdad${\displaystyle \delta (G)\geq k-1}$. Es decir, cada vértice es adyacente a al menos${\displaystyle k-1}$otros. Con mayor fuerza,${\displaystyle G}$es${\displaystyle (k-1)}$- conectado por aristas . ^{[ 2 ]}
• Si${\displaystyle G}$es un grafo regular con grado${\displaystyle k-1}$, lo que significa que cada vértice es adyacente a exactamente${\displaystyle k-1}$otros, entonces${\displaystyle G}$es el gráfico completo${\displaystyle K_{k}}$con${\displaystyle n=k}$vértices, o un grafo de ciclo de longitud impar . Este es el teorema de Brooks . ^{[ 3 ]}
• ${\displaystyle 2m\geq (k-1)n+k-3}$. ^{[ 4 ]}
• ${\displaystyle 2m\geq (k-1)n+(k-3)/(k^{2}-3)n}$. ^{[ 5 ]}
• Cualquiera${\displaystyle G}$puede descomponerse en dos grafos críticos más pequeños, con una arista entre cada par de vértices que incluye un vértice de cada uno de los dos subgrafos, o${\displaystyle G}$tiene al menos${\displaystyle 2k-1}$vértices. ^{[ 6 ]} Más fuertemente, o bien${\displaystyle G}$tiene una descomposición de este tipo, o para cada vértice${\displaystyle v}$de${\displaystyle G}$hay un${\displaystyle k}$-coloración en la que${\displaystyle v}$es el único vértice de su color y todas las demás clases de color tienen al menos dos vértices. ^{[ 7 ]}

Gráfico${\displaystyle G}$es crítico para los vértices si y solo si para cada vértice${\displaystyle v}$, existe una coloración óptima adecuada en la que${\displaystyle v}$es una clase de color única.

Como demostró Hajós (1961) , cada${\displaystyle k}$-El gráfico crítico puede formarse a partir de un gráfico completo.${\displaystyle K_{k}}$mediante la combinación de 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${\displaystyle k}$colores en cualquier coloración adecuada. ^{[ 8 ]}

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

• Gráfico factor-crítico