Gráfico crítico

Grafo no dirigido

En la parte superior izquierda un grafo crítico de vértice con número cromático 6; a continuación todos los N-1 subgrafos con número cromático 5.

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 la cantidad de colores necesarios para colorear el grafo dado. Cada vez que se elimina una sola arista o vértice (junto con sus aristas incidentes) de un grafo crítico, la disminución en la cantidad de colores necesarios para colorear ese grafo no puede ser mayor que uno.

Variaciones

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. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle k}$

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

• ${\displaystyle G}$tiene solo un componente
• ${\displaystyle 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}$ ${\displaystyle k-1}$ ${\displaystyle G}$ ${\displaystyle (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] ${\displaystyle G}$ ${\displaystyle k-1}$ ${\displaystyle k-1}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$ ${\displaystyle n=k}$
• ${\displaystyle 2m\geq (k-1)n+k-3}$. ^[4]
• ${\displaystyle 2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor 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] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle 2k-1}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle 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. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle 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] ${\displaystyle k}$ ${\displaystyle K_{k}}$ ${\displaystyle 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] ${\displaystyle K_{k}}$ ${\displaystyle k}$

Véase también

• Gráfica de factores críticos

Referencias

1. de Bruijn, NG ; Erdős, P. (1951), "Un problema de color para gráficos infinitos y un problema de teoría de relaciones", Nederl. Akád. Wetensch. Proc. Ser. A , 54 : 371–373, CiteSeerX  10.1.1.210.6623 , doi : 10.1016/S1385-7258(51)50053-7. ( Matemáticas Indag. 13 .)
2. Lovász, László (1992), "Solución del ejercicio 9.21", Problemas y ejercicios combinatorios (2ª ed.), Holanda Septentrional, ISBN 978-0-8218-6947-5
3. Brooks, RL (1941), "Sobre la coloración de los nodos de una red", Actas de la Sociedad Filosófica de Cambridge , 37 (2): 194–197, Bibcode :1941PCPS...37..194B, doi :10.1017/S030500410002168X, S2CID  209835194
4. Dirac, GA (1957), "Un teorema de RL Brooks y una conjetura de H. Hadwiger", Actas de la London Mathematical Society , 7 (1): 161–195, doi :10.1112/plms/s3-7.1.161
5. Gallai, T. (1963), "Kritische Graphen I", Publ. Matemáticas. Inst. Hungría. Acad. Ciencia. , 8 : 165-192
6. Gallai, T. (1963), "Kritische Graphen II", Publ. Matemáticas. Inst. Hungría. Acad. Ciencia. , 8 : 373–395
7. Stehlík, Matěj (2003), "Grafos críticos con complementos conexos", Journal of Combinatorial Theory , Serie B, 89 (2): 189–194, doi :10.1016/S0095-8956(03)00069-8, MR  2017723
8. Hajós, G. (1961), "Über eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe , 10 : 116-117
9. Erdős, Paul (1967), "Problema 2", en Teoría de grafos , Proc. Coloq., Tihany, pág. 361

Lectura adicional

• Jensen, TR; Toft, B. (1995), Problemas de coloración de gráficos , Nueva York: Wiley-Interscience, ISBN 0-471-02865-7
• Stiebitz, Michael; Tuza, Zsolt; Voigt, Margit (6 de agosto de 2009), "Sobre los grafos críticos de listas", Discrete Mathematics , 309 (15), Elsevier: 4931–4941, doi :10.1016/j.disc.2008.05.021