Gráfico crítico

Un gráfico crítico  es un gráfico en el que la eliminación de cualquier vértice o borde reduce el número cromático del gráfico.

Definiciones relacionadas

• -grafo critico  es un grafo critico con numero cromatico k .
• Un grafo G con número cromático k es vértice - k -crítico si cada uno de sus vértices es un elemento crítico [1] .

Propiedades

• Sea G un grafo k -crítico con n vértices y m aristas. Después:
  • G tiene un solo componente .
  • G es finito ( teorema de de Bruijn-Erdős [2] ).
  • δ( G ) ≥ k − 1, es decir, cualquier vértice es adyacente a al menos k  − 1 otros vértices. Más estrictamente, G es ( k  − 1) -conectado por arista [3] .
  • Si el gráfico G es ( k  − 1)-regular (cada vértice es adyacente a exactamente k  − 1 otros), entonces el gráfico G es un gráfico completo K k o un ciclo impar . (Este es el teorema de Brooks [4] ).
  • 2 metro ≥ ( k - 1) norte + k - 3 [5] .
  • 2 metro ≥ ( k - 1) norte + [( k - 3)/( k 2 - 3)] norte [6] .
  • O G se puede dividir en dos gráficos críticos más pequeños con un borde entre cada par de vértices, donde dos vértices provienen de partes diferentes, o G tiene al menos 2k  - 1 vértices [7] . Más estrictamente, G tiene descomposiciones de este tipo, o para cada vértice v del grafo G hay una coloración k en la que v es el único vértice con su propio color, y todas las demás clases de color tienen al menos dos vértices [8 ] .

• Un grafo G es crítico para el vértice si y solo si para cualquier vértice v existe una coloración adecuada óptima en la que el vértice v solo representa la clase de color.

• 1-los gráficos críticos no existen.
• El único gráfico 2-crítico es K 2 .
• Todos los gráficos de 3 críticos se agotan en ciclos simples de longitud impar [9] .

• Como mostró Hajos [10] , cualquier gráfico k -crítico puede formarse a partir de un gráfico K k completo combinando la construcción de Hajos con la operación de identificar dos vértices no adyacentes. El gráfico formado de esta manera siempre requiere k colores en cualquier coloración adecuada.

• Aunque todo gráfico de línea crítica es necesariamente crítico, lo contrario no es cierto. Por ejemplo, el gráfico de la derecha es 4-crítico pero no crítico para los bordes [11] .

Variaciones y generalizaciones

• 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. Uno de los problemas no resueltos es si K k es el único gráfico k - cromático doblemente crítico [12] .

Véase también

• Gráfico de factor crítico

Notas

1. ↑ Cabe señalar que un gráfico crítico no siempre se entiende como un gráfico k -cromático crítico. En el artículo de Vizing, un gráfico crítico de dimensión k se entiende como un gráfico cuya dimensión de cualquier parte propia es menor que k. En este caso, la dimensión de un grafo se entiende como la dimensión mínima de un espacio métrico en el que se puede incrustar el grafo de modo que todos los vértices adyacentes estén a una distancia de 1. ( Vizing 1968 )
2. ↑ de Bruijn, Erdős, 1951 .
3. ↑ Lovasz, 1992 .
4. ↑ Brooks, Tutte, 1941 .
5. ↑ Dirac, 1957 .
6. ↑ Gallai, 1963a .
7. ↑ Gallai, 1963b .
8. ↑ Stehlik, 2003 .
9. ↑ Harari, 2003 , pág. 167.
10. ↑ Hajos, 1961 .
11. ↑ Harari, 2003 , pág. 168-169.
12. ↑ Erdős, 1966 .

Literatura

• R. L. Brooks, W. T. Tutte. Sobre colorear los nodos de una red // Actas de la Sociedad Filosófica de Cambridge. - 1941. - T. 37 , núm. 02 . — S. 194–197 . -doi : 10.1017/ S030500410002168X .
• N. G. de Bruijn , P. Erdős . Un problema de color para grafos infinitos y un problema de teoría de relaciones // Nederl. Akád. Wetensch. proc. Ser. A.- 1951.- T. 54 . — S. 371–373 . . ( Indag. Matemáticas 13.)
• GA Dirac. Un teorema de RL Brooks y una conjetura de H. Hadwiger // Actas de la London Mathematical Society. - 1957. - T. 7 , núm. 1 . — S. 161–195 . -doi : 10.1112 / plms/s3-7.1.161 .
• T. Gallai. Kritische Graphen I // Publ. Matemáticas. Inst. hungaro Academia Esc.. - 1963a. - T. 8 . — S. 165–192 .
• T. Gallai. Kritische Graphen II // Publ. Matemáticas. Inst. hungaro Academia Esc.. - 1963b. - T. 8 . — S. 373–395 . .
• G. Hajos . Uber eine Konstruktion nicht n -färbbarer Graphen // Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe. - 1961. - T. 10 . — S. 116–117 .
• TR Jensen, B. Toft. Problemas de coloreado de gráficas. - Nueva York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
• Matj Stehlik. Gráficos críticos con complementos conectados // Journal of Combinatorial Theory . - 2003. - T. 89 , núm. 2 . — S. 189–194 . - doi : 10.1016/S0095-8956(03)00069-8 .
• Laszlo Lovasz . Problemas y ejercicios combinatorios (segunda edición). — Holanda Septentrional, 1992.
• Pablo Erds . En Teoría de Grafos. — Proc. Colloq., Tihany, 1966. - Pág. 361.
• V. G. Vizing. Algunos problemas no resueltos en teoría de grafos // Uspekhi Matematicheskikh Nauk. - 1968. - T. XXIII , núm. 6 (144) . — págs. 117–134 .
• F. Harari. Teoría de grafos. - 2do. - M. : Editorial URSS, 2003. - ISBN 5-354-00301-6 , BBC 22.144, 22.18, 22.19.