Gráfico perfecto

Graph with tight clique-coloring relation

El gráfico del duoprisma 3-3 (el gráfico lineal de ) es perfecto. Aquí está coloreado con tres colores, con una de sus camarillas máximas de 3 vértices resaltada. ${\displaystyle K_{3,3}}$

En teoría de grafos , un grafo perfecto es un grafo en el que el número cromático es igual al tamaño de la camarilla máxima , tanto en el propio grafo como en cada subgrafo inducido . En todos los grafos, el número cromático es mayor o igual que el tamaño de la camarilla máxima, pero pueden estar muy separados. Un grafo es perfecto cuando estos números son iguales y permanecen iguales después de la eliminación de subconjuntos arbitrarios de vértices.

Los grafos perfectos incluyen muchas familias importantes de grafos y sirven para unificar resultados que relacionan coloraciones y camarillas en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos , el problema de camarilla máxima y el problema de conjunto independiente máximo pueden resolverse en tiempo polinomial , a pesar de su mayor complejidad para grafos no perfectos. Además, varios teoremas minimax importantes en combinatoria , incluidos el teorema de Dilworth y el teorema de Mirsky sobre conjuntos parcialmente ordenados , el teorema de Kőnig sobre emparejamientos y el teorema de Erdős–Szekeres sobre secuencias monótonas, pueden expresarse en términos de la perfección de ciertos grafos asociados.

El teorema del grafo perfecto establece que el grafo complementario de un grafo perfecto también es perfecto. El teorema del grafo perfecto fuerte caracteriza a los grafos perfectos en términos de ciertos subgrafos inducidos prohibidos , lo que conduce a un algoritmo de tiempo polinomial para comprobar si un grafo es perfecto.

Definiciones y caracterizaciones

Un ciclo de siete vértices y su complemento, que muestra en cada caso una coloración óptima y un grupo máximo (mostrados con bordes gruesos). Ninguno de los gráficos utiliza una cantidad de colores igual al tamaño de su grupo, por lo que ninguno es perfecto.

Una camarilla en un grafo no dirigido es un subconjunto de sus vértices que son todos adyacentes entre sí, como los subconjuntos de vértices conectados por aristas gruesas en la ilustración. El número de camarilla es el número de vértices en la camarilla más grande: dos en el ciclo de siete vértices ilustrado y tres en el otro grafo mostrado. Una coloración de grafo asigna un color a cada vértice de modo que cada dos vértices adyacentes tengan colores diferentes, también mostrados en la ilustración. El número cromático de un grafo es el número mínimo de colores en cualquier coloración. Las coloraciones mostradas son óptimas, por lo que el número cromático es tres para el ciclo de 7 y cuatro para el otro grafo mostrado. Los vértices de cualquier camarilla deben tener colores diferentes, por lo que el número cromático siempre es mayor o igual que el número de camarilla. Para algunos grafos, son iguales; para otros, como los que se muestran, son desiguales. Los grafos perfectos se definen como los grafos para los cuales estos dos números son iguales, no sólo en el grafo mismo, sino en cada subgrafo inducido obtenido al eliminar algunos de sus vértices. ^[1]

Dos gráficos perfectos complementarios

El teorema del grafo perfecto afirma que el grafo complementario de un grafo perfecto es en sí mismo perfecto. El grafo complementario tiene una arista entre dos vértices si y solo si el grafo dado no la tiene. Una camarilla, en el grafo complementario, corresponde a un conjunto independiente en el dado. Una coloración del grafo complementario corresponde a una cobertura de camarilla , una partición de los vértices del grafo dado en camarillas. El hecho de que el complemento de un grafo perfecto también sea perfecto implica que, en sí mismo, el número de independencia (el tamaño de su conjunto independiente máximo ), es igual a su número de cobertura de camarilla (el menor número de camarillas necesarias en una cobertura de camarilla). Más fuertemente, lo mismo es cierto en cada subgrafo inducido del grafo complementario. Esto proporciona una definición alternativa y equivalente de los grafos perfectos: son los grafos para los cuales, en cada subgrafo inducido, el número de independencia es igual al número de cobertura de camarilla. ^{[2] [3]} ${\displaystyle G}$ ${\displaystyle G}$

El teorema del grafo perfecto fuerte ofrece una forma diferente de definir los grafos perfectos, por su estructura en lugar de por sus propiedades. Se basa en la existencia de grafos de ciclo y sus complementos dentro de un grafo dado. Un ciclo de longitud impar, mayor que tres, no es perfecto: su número de clique es dos, pero su número cromático es tres. Por el teorema del grafo perfecto, el complemento de un ciclo impar de longitud mayor que tres tampoco es perfecto. El complemento de un ciclo de longitud 5 es otro ciclo de longitud 5, pero para longitudes impares mayores el complemento no es un ciclo; se llama anticiclo . El teorema del grafo perfecto fuerte afirma que estos son los únicos subgrafos inducidos prohibidos para los grafos perfectos: un grafo es perfecto si y solo si sus subgrafos inducidos no incluyen ni un ciclo impar ni un anticiclo impar de cinco o más vértices. En este contexto, los ciclos inducidos que no son triángulos se denominan "agujeros", y sus complementos se denominan "antiagujeros", por lo que el teorema del grafo perfecto fuerte se puede formular de forma más sucinta: un grafo es perfecto si y solo si no tiene ni un agujero impar ni un antiagujero impar. ^[4]

Estos resultados pueden combinarse en otra caracterización de los grafos perfectos: son los grafos para los cuales el producto del número de camarilla y el número de independencia es mayor o igual que el número de vértices, y para los cuales lo mismo es cierto para todos los subgrafos inducidos. Debido a que el enunciado de esta caracterización permanece invariante bajo complementación de grafos, implica el teorema del grafo perfecto. Una dirección de esta caracterización se sigue fácilmente de la definición original de perfecto: el número de vértices en cualquier grafo es igual a la suma de los tamaños de las clases de color en una coloración óptima, y ​​es menor o igual que el número de colores multiplicado por el número de independencia. En un grafo perfecto, el número de colores es igual al número de camarilla, y puede reemplazarse por el número de camarilla en esta desigualdad. La otra dirección se puede demostrar directamente, ^{[5] [6]} pero también se deduce del teorema del grafo perfecto fuerte: si un grafo no es perfecto, contiene un ciclo impar o su complemento, y en estos subgrafos el producto del número de camarilla y el número de independencia es uno menos que el número de vértices. ^[7]

Historia

La teoría de grafos perfectos se desarrolló a partir de un resultado de 1958 de Tibor Gallai que en lenguaje moderno puede interpretarse como que el complemento de un grafo bipartito es perfecto; ^[8] este resultado también puede verse como un equivalente simple del teorema de Kőnig , un resultado mucho anterior que relaciona emparejamientos y recubrimientos de vértices en grafos bipartitos. La primera formulación del concepto de grafos perfectos de manera más general fue en un artículo de 1961 de Claude Berge , en alemán, ^[9] y el primer uso de la frase "grafo perfecto" parece ser en un artículo de 1963 de Berge. ^[10] En estos trabajos unificó el resultado de Gallai con varios resultados similares al definir grafos perfectos, y conjeturó tanto el teorema del grafo perfecto como el teorema del grafo perfecto fuerte. Al formular estos conceptos, Berge estuvo motivado por el concepto de capacidad de Shannon de un grafo , por el hecho de que para grafos (co-)perfectos es igual al número de independencia, y por la búsqueda de ejemplos mínimos de grafos para los cuales este no es el caso. ^[11] Hasta que se demostró el teorema del grafo perfecto fuerte, los grafos descritos por él (es decir, los grafos sin agujero impar y sin antiagujero impar) se llamaban grafos de Berge . ^[12]

El teorema del grafo perfecto fue demostrado por László Lovász en 1972, ^[2] quien en el mismo año demostró la desigualdad más fuerte entre el número de vértices y el producto del número de camarilla y el número de independencia, sin el beneficio del teorema del grafo perfecto fuerte. ^[5] En 1991, Alfred Lehman ganó el Premio Fulkerson , patrocinado conjuntamente por la Mathematical Optimization Society y la American Mathematical Society , por su trabajo sobre generalizaciones de la teoría de grafos perfectos a matrices lógicas . ^[13] El conjeturado teorema del grafo perfecto fuerte se convirtió en el foco de investigación en la teoría de grafos perfectos durante muchos años, ^[12] hasta que su prueba fue anunciada en 2002 por Maria Chudnovsky , Neil Robertson , Paul Seymour y Robin Thomas , ^[14] y publicada por ellos en 2006. ^[4] Este trabajo le valió a sus autores el Premio Fulkerson 2009. ^[15] El teorema del grafo perfecto tiene una prueba corta, ^{[5] [6]} pero la prueba del teorema fuerte del grafo perfecto es larga y técnica, basada en una descomposición estructural profunda de los grafos de Berge. Las técnicas de descomposición relacionadas también han dado frutos en el estudio de otras clases de grafos, y en particular para los grafos sin garras . ^[16] La caracterización simétrica de los grafos perfectos en términos del producto del número de camarilla y el número de independencia fue sugerida originalmente por Hajnal y probada por Lovász. ^[5]

Familias de grafos

Muchas familias de grafos bien estudiadas son perfectas, ^[12] y en muchos casos el hecho de que estos grafos sean perfectos corresponde a un teorema minimax para algunos tipos de estructura combinatoria definida por estos grafos. Ejemplos de este fenómeno incluyen la perfección de grafos bipartitos y sus grafos lineales , asociados con el teorema de Kőnig que relaciona los emparejamientos máximos y las coberturas de vértices en grafos bipartitos, y la perfección de grafos de comparabilidad , asociados con el teorema de Dilworth y el teorema de Mirsky sobre cadenas y anticadenas en conjuntos parcialmente ordenados . Otras clases importantes de grafos, definidas por tener una estructura relacionada con los huecos y antihuecos del teorema fuerte del grafo perfecto, incluyen los grafos cordales , los grafos de Meyniel y sus subclases.

Gráficos bipartitos y gráficos lineales

Un gráfico bipartito (izquierda) y su gráfico lineal (derecha). Las camarillas sombreadas en el gráfico lineal corresponden a los vértices del gráfico bipartito subyacente y tienen un tamaño igual al grado del vértice correspondiente.

En los grafos bipartitos (con al menos una arista) el número cromático y el número de camarilla son ambos iguales a dos. Sus subgrafos inducidos siguen siendo bipartitos, por lo que los grafos bipartitos son perfectos. ^[12] Otras familias importantes de grafos son bipartitas y, por lo tanto, también perfectas, incluyendo, por ejemplo, los árboles y los grafos medianos . ^[17] Por el teorema del grafo perfecto, los conjuntos independientes máximos en grafos bipartitos tienen el mismo tamaño que sus coberturas de camarilla mínimas. El conjunto independiente máximo es complementario a una cobertura de vértices mínima , un conjunto de vértices que toca todas las aristas. Una cobertura de camarilla mínima consiste en una coincidencia máxima (tantas aristas disjuntas como sea posible) junto con camarillas de un vértice para todos los vértices restantes, y su tamaño es el número de vértices menos el número de aristas coincidentes. Por lo tanto, esta igualdad se puede expresar de forma equivalente como una igualdad entre el tamaño de la coincidencia máxima y la cobertura de vértices mínima en grafos bipartitos, la formulación habitual del teorema de Kőnig . ^{[18] [19]}

Un emparejamiento, en cualquier grafo , es lo mismo que un conjunto independiente en el grafo lineal , un grafo que tiene un vértice para cada arista en y una arista entre dos vértices en para cada par de aristas en que comparten un punto final. Los grafos lineales tienen dos tipos de camarillas: conjuntos de aristas en con un punto final común y triángulos en . En los grafos bipartitos, no hay triángulos, por lo que una cobertura de camarilla en corresponde a una cobertura de vértice en . Por lo tanto, en los grafos lineales de grafos bipartitos, el número de independencia y el número de cobertura de camarilla son iguales. Los subgrafos inducidos de los grafos lineales de los grafos bipartitos son grafos lineales de subgrafos, por lo que los grafos lineales de los grafos bipartitos son perfectos. ^[19] Los ejemplos incluyen los grafos de torre , los grafos lineales de grafos bipartitos completos . Cada grafo lineal de un grafo bipartito es un subgrafo inducido de un grafo de torre. ^[20] ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle G}$

Debido a que los gráficos lineales de los grafos bipartitos son perfectos, su número de clique es igual a su número cromático. El número de clique del gráfico lineal de un grafo bipartito es el grado máximo de cualquier vértice del grafo bipartito subyacente. El número cromático del gráfico lineal de un grafo bipartito es el índice cromático del grafo bipartito subyacente, el número mínimo de colores necesarios para colorear los bordes de modo que los bordes en contacto tengan colores diferentes. Cada clase de color forma una coincidencia, y el índice cromático es el número mínimo de coincidencias necesarias para cubrir todos los bordes. La igualdad del grado máximo y el índice cromático, en grafos bipartitos, es otro teorema de Dénes Kőnig . ^[21] En grafos simples arbitrarios, pueden diferir en uno; este es el teorema de Vizing . ^[19]

Un gráfico de línea perfecta , con componentes bipartitos biconectados negros, libros triangulares azules y rojos. ${\displaystyle K_{4}}$

El gráfico subyacente de un gráfico lineal perfecto es un gráfico lineal perfecto . Estos son los gráficos cuyos componentes biconectados son los grafos bipartitos, el gráfico completo y los triángulos triangulares , conjuntos de triángulos que comparten una arista. Estos componentes son perfectos y su combinación preserva la perfección, por lo que todo gráfico lineal perfecto es perfecto. ^[19] ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle K_{4}}$

Los grafos bipartitos, sus complementos y los grafos lineales de grafos bipartitos y sus complementos forman cuatro clases básicas de grafos perfectos que desempeñan un papel clave en la demostración del teorema fuerte del grafo perfecto. De acuerdo con la descomposición estructural de grafos perfectos utilizada como parte de esta demostración, todo grafo perfecto que no esté ya en una de estas cuatro clases se puede descomponer dividiendo sus vértices en subconjuntos, de una de cuatro maneras, llamadas 2-join, el complemento de un 2-join, un par homogéneo o una partición oblicua . ^[3]

Gráficos de comparabilidad

Diagrama de Hasse de un conjunto parcialmente ordenado y su gráfico de comparabilidad

Un conjunto parcialmente ordenado se define por su conjunto de elementos y una relación de comparación que es reflexiva (para todos los elementos , ), antisimétrica (si y , entonces , y transitiva (si y , entonces ). Los elementos y son comparables si o , e incomparables en caso contrario. Por ejemplo, la inclusión de conjuntos ( ) ordena parcialmente cualquier familia de conjuntos . El gráfico de comparabilidad de un conjunto parcialmente ordenado tiene los elementos del conjunto como sus vértices, con una arista que conecta dos elementos comparables cualesquiera. Su complemento se llama gráfico de incomparabilidad . Diferentes órdenes parciales pueden tener el mismo gráfico de comparabilidad; por ejemplo, invertir todas las comparaciones cambia el orden pero no el gráfico. ^[22] ${\displaystyle \leq }$ ${\displaystyle x}$ ${\displaystyle x\leq x}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle x=y}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq z}$ ${\displaystyle x\leq z}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\leq y}$ ${\displaystyle y\leq x}$ ${\displaystyle \subseteq }$

Los gráficos de comparabilidad finitos (y sus gráficos de incomparabilidad complementarios) son siempre perfectos. ^[23] Una camarilla, en un gráfico de comparabilidad, proviene de un subconjunto de elementos que son todos comparables por pares; dicho subconjunto se llama cadena y está ordenado linealmente por el orden parcial dado. Un conjunto independiente proviene de un subconjunto de elementos de los cuales ninguno de los dos es comparable; dicho subconjunto se llama anticadena . Por ejemplo, en el gráfico de orden parcial y comparabilidad ilustrado, es una cadena en el orden y una camarilla en el gráfico, mientras que es una anticadena en el orden y un conjunto independiente en el gráfico. Por lo tanto, una coloración de un gráfico de comparabilidad es una partición de sus elementos en anticadenas, y una cobertura de camarilla es una partición de sus elementos en cadenas. El teorema de Dilworth , en la teoría de órdenes parciales, establece que para cada orden parcial finito, el tamaño de la anticadena más grande es igual al número mínimo de cadenas en las que se pueden dividir los elementos. En el lenguaje de los grafos, esto se puede expresar como: todo grafo de comparabilidad finito es perfecto. De manera similar, el teorema de Mirsky establece que para cada orden parcial finito, el tamaño de la cadena más grande es igual al número mínimo de anticadenas en las que se pueden dividir los elementos, o que todo grafo de incomparabilidad finito es perfecto. Estos dos teoremas son equivalentes a través del teorema del grafo perfecto, pero el teorema de Mirsky es más fácil de demostrar directamente que el teorema de Dilworth: si cada elemento está etiquetado por el tamaño de la cadena más grande en la que es máximo, entonces los subconjuntos con etiquetas iguales forman una partición en anticadenas, con el número de anticadenas igual al tamaño de la cadena más grande en general. ^[24] Todo grafo bipartito es un grafo de comparabilidad. Por lo tanto, el teorema de Kőnig puede verse como un caso especial del teorema de Dilworth, conectado a través de la teoría de grafos perfectos. ^[25] ${\displaystyle \{A,B,C\}}$ ${\displaystyle \{C,D\}}$

El gráfico de permutación de la permutación (4,3,5,1,2) conecta pares de elementos cuyo orden se invierte por la permutación.

Un grafo de permutación se define a partir de una permutación sobre una secuencia totalmente ordenada de elementos (convencionalmente, los números enteros de a ), que forman los vértices del grafo. Las aristas de un grafo de permutación conectan pares de elementos cuyo ordenamiento se invierte por la permutación dada. Estos son naturalmente grafos de incomparabilidad, para un orden parcial en el que siempre que ocurre antes tanto en la secuencia dada como en su permutación. El complemento de un grafo de permutación es otro grafo de permutación, para el reverso de la permutación dada. Por lo tanto, además de ser grafos de incomparabilidad, los grafos de permutación son grafos de comparabilidad. De hecho, los grafos de permutación son exactamente los grafos que son a la vez grafos de comparabilidad e incomparabilidad. ^[26] Una camarilla, en un grafo de permutación, es una subsecuencia de elementos que aparecen en orden creciente en la permutación dada, y un conjunto independiente es una subsecuencia de elementos que aparecen en orden decreciente. En cualquier gráfico perfecto, el producto del número de camarilla y el número de independencia es al menos el número de vértices; el caso especial de esta desigualdad para gráficos de permutación es el teorema de Erdős–Szekeres . ^[24] ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle y}$

Un gráfico de intervalos y los intervalos que lo definen

Los gráficos de intervalos son los gráficos de incomparabilidad de los órdenes de intervalos , ordenamientos definidos por conjuntos de intervalos en la línea real con siempre que el intervalo esté completamente a la izquierda del intervalo . En el gráfico de intervalos correspondiente, hay una arista desde hasta siempre que los dos intervalos tengan un punto en común. La coloración de estos gráficos se puede utilizar para modelar problemas de asignación de recursos a tareas (como aulas a clases) con intervalos que describen el tiempo programado de cada tarea. ^[27] Tanto los gráficos de intervalos como los gráficos de permutación se generalizan mediante los gráficos trapezoidales . ^[28] Los sistemas de intervalos en los que no hay dos anidados producen una clase más restringida de gráficos, los gráficos de indiferencia , los gráficos de incomparabilidad de semiórdenes . Estos se han utilizado para modelar las preferencias humanas bajo el supuesto de que, cuando los elementos tienen utilidades muy cercanas entre sí, serán incomparables. ^[29] Los intervalos donde cada par está anidado o disjunto producen gráficos trivialmente perfectos , ^[30] los gráficos de comparabilidad de árboles ordenados . En ellos, el número de independencia es igual al número de camarillas máximas . ^[31] ${\displaystyle x\leq y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$

Gráficos divididos y gráficos perfectos aleatorios

Coloración óptima de un gráfico dividido , obtenida al dar a cada vértice de una camarilla máxima (vértices y aristas pesadas) un color separado, y luego dar a cada vértice restante el mismo color que un vértice de la camarilla al que no es adyacente

Un grafo dividido es un grafo que se puede dividir en una camarilla y un conjunto independiente. Se puede colorear asignando un color separado a cada vértice de una camarilla máxima y luego coloreando cada vértice restante del mismo modo que un vértice de camarilla no adyacente. Por lo tanto, estos grafos tienen números de camarilla y números cromáticos iguales, y son perfectos. ^[32] Una clase más amplia de grafos, los grafos unipolares se pueden dividir en una camarilla y un grafo de clúster , una unión disjunta de camarillas. Estos incluyen también los grafos bipartitos, para los cuales el grafo de clúster es solo una camarilla única. Los grafos unipolares y sus complementos juntos forman la clase de grafos divididos generalizados . Casi todos los grafos perfectos son grafos divididos generalizados, en el sentido de que la fracción de grafos de vértice perfectos que son grafos divididos generalizados tiende a uno en el límite a medida que crece arbitrariamente. ^[33] ${\displaystyle n}$ ${\displaystyle n}$

Otras propiedades limitantes de casi todos los grafos perfectos pueden determinarse estudiando los grafos divididos generalizados. De esta manera, se ha demostrado que casi todos los grafos perfectos contienen un ciclo hamiltoniano . Si es un grafo arbitrario, la probabilidad limitante de que ocurra como un subgrafo inducido de un grafo perfecto aleatorio grande es 0, 1/2 o 1, respectivamente, ya que no es un grafo dividido generalizado, es unipolar o counipolar pero no ambos, o es tanto unipolar como counipolar. ^[34] ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H}$

Construcciones incrementales

Varias familias de grafos perfectos pueden caracterizarse por una construcción incremental en la que los grafos de la familia se construyen añadiendo un vértice a la vez, de acuerdo con ciertas reglas, que garantizan que después de añadir cada vértice el grafo siga siendo perfecto.

• Los grafos cordales son los grafos formados por una construcción de este tipo en la que, en el momento en que se añade un vértice, sus vecinos forman una camarilla. Los grafos cordales también pueden caracterizarse como los grafos que no tienen agujeros (pares o impares). ^[35] Incluyen como casos especiales los bosques, los grafos de intervalo, ^[36] y los grafos maximal outerplanares . ^[37] Los grafos split son precisamente los grafos que son cordales y tienen un complemento cordal. ^[38] Los k -árboles , centrales para la definición de treewidth , son grafos cordales formados partiendo de una camarilla de ( k + 1) -vértice y añadiendo repetidamente un vértice de forma que éste y sus vecinos formen una camarilla del mismo tamaño. ^[35]

Tres tipos de adición de vértices en un gráfico hereditario de distancia

• Los grafos hereditarios de distancia se forman, a partir de un grafo de un solo vértice, añadiendo repetidamente vértices de grado uno ("vértices colgantes") o copias de vértices existentes (con los mismos vecinos). Cada vértice y su copia pueden ser adyacentes ( gemelos verdaderos ) o no adyacentes ( gemelos falsos ). En cada subgrafo inducido conexo de estos grafos, las distancias entre vértices son las mismas que en el grafo completo. Si solo se utilizan las operaciones de gemelos, el resultado es un cografo . ^[39] Los cografos son los grafos de comparabilidad de órdenes parciales serie-paralelos ^[40] y también pueden formarse mediante un proceso de construcción diferente que combina la complementación y la unión disjunta de grafos . ^[41]
• Los grafos que son a la vez cordales y hereditarios de la distancia se denominan grafos ptolemaicos , porque sus distancias obedecen a la desigualdad de Ptolomeo . ^[42] Tienen una forma restringida de la secuencia de construcción hereditaria de la distancia, en la que un falso gemelo solo se puede agregar cuando sus vecinos formarían una camarilla. ^[39] Incluyen como casos especiales los grafos de molino de viento que consisten en camarillas unidas en un solo vértice, y los grafos de bloque en los que cada componente biconectado es una camarilla. ^[42]
• Los grafos de umbral se forman a partir de un grafo vacío añadiendo repetidamente un vértice aislado (conectado a nada más) o un vértice universal (conectado a todos los demás vértices). ^[43] Son casos especiales de los grafos divididos y los grafos trivialmente perfectos. Son exactamente los grafos que son a la vez trivialmente perfectos y el complemento de un grafo trivialmente perfecto; también son exactamente los grafos que son a la vez cografos y grafos divididos. ^[44]

Si los vértices de un grafo cordal se colorean en el orden de una secuencia de construcción incremental utilizando un algoritmo de coloración voraz , el resultado será una coloración óptima. El orden inverso del vértice utilizado en esta construcción se denomina orden de eliminación . ^[45] De manera similar, si los vértices de un grafo hereditario de distancia se colorean en el orden de una secuencia de construcción incremental, la coloración resultante será óptima. ^[46] Si los vértices de un grafo de comparabilidad se colorean en el orden de una extensión lineal de su orden parcial subyacente, la coloración resultante será óptima. Esta propiedad se generaliza en la familia de grafos perfectamente ordenables , los grafos para los que existe un ordenamiento que, cuando se restringe a cualquier subgrafo inducido, hace que la coloración voraz sea óptima. ^[47] Los cografos son exactamente los grafos para los que todos los ordenamientos de vértices tienen esta propiedad. ^[48] Otra subclase de grafos perfectamente ordenables son los complementos de los grafos de tolerancia , una generalización de los grafos de intervalo. ^[49]

Fuerte perfección

Los grafos fuertemente perfectos son grafos en los que, en cada subgrafo inducido, existe un conjunto independiente que interseca a todos los cliques maximalistas . En los grafos de Meyniel o grafos muy fuertemente perfectos , cada vértice pertenece a dicho conjunto independiente. Los grafos de Meyniel también pueden caracterizarse como los grafos en los que cada ciclo impar de longitud cinco o más tiene al menos dos cuerdas. ^[50]

Un gráfico de paridad que no es ni hereditario de la distancia ni bipartito

Un grafo de paridad se define por la propiedad de que entre cada dos vértices, todos los caminos inducidos tienen la misma paridad: o son todos pares en longitud, o son todos impares en longitud. Estos incluyen los grafos hereditarios de distancia, en los que todos los caminos inducidos entre dos vértices tienen la misma longitud, ^[51] y los grafos bipartitos, para los que todos los caminos (no sólo los caminos inducidos) entre dos vértices cualesquiera tienen la misma paridad. Los grafos de paridad son grafos de Meyniel, y por lo tanto perfectos: si un ciclo impar largo tuviera sólo una cuerda, las dos partes del ciclo entre los puntos finales de la cuerda serían caminos inducidos de diferente paridad. El prisma sobre cualquier grafo de paridad (su producto cartesiano con una sola arista) es otro grafo de paridad, y los grafos de paridad son los únicos grafos cuyos prismas son perfectos. ^[52]

Matrices, poliedros y programación entera

Los grafos perfectos están estrechamente relacionados con la teoría de la programación lineal y la programación entera . Tanto los programas lineales como los enteros se expresan en forma canónica como la búsqueda de un vector que maximice una función objetivo lineal , sujeta a las restricciones lineales y . Aquí, se da como una matriz , y y se dan como dos vectores. Aunque los programas lineales y los enteros se especifican de esta misma manera, difieren en que, en un programa lineal, se permite que el vector solución tenga números reales arbitrarios como sus coeficientes, mientras que en un programa entero estos coeficientes desconocidos deben ser enteros. Esto hace una gran diferencia en la complejidad computacional de estos problemas: la programación lineal se puede resolver en tiempo polinomial , pero la programación entera es NP-hard . ^[1] ${\displaystyle x}$ ${\displaystyle c\cdot x}$ ${\displaystyle x\geq 0}$ ${\displaystyle Ax\leq b}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle x}$

Cuando se utilizan los mismos valores dados , , y para definir tanto un programa lineal como un programa entero, comúnmente tienen diferentes soluciones óptimas. El programa lineal se denomina programa lineal integral si una solución óptima para el programa entero también es óptima para el programa lineal. (De lo contrario, la relación entre los dos valores de solución se denomina brecha de integralidad y es importante para analizar algoritmos de aproximación para el programa entero). Los gráficos perfectos se pueden utilizar para caracterizar las matrices (0, 1) (es decir, matrices donde todos los coeficientes son 0 o 1) con la siguiente propiedad: si es el vector de todos los unos , entonces para todas las opciones del programa lineal resultante es integral. ^[1] ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle A}$ ${\displaystyle b}$ ${\displaystyle c}$

Como demostró Václav Chvátal , cada matriz con esta propiedad es (hasta la eliminación de filas "dominadas" irrelevantes) la matriz de incidencia máxima de clique versus vértice de un grafo perfecto. Esta matriz tiene una columna para cada vértice del grafo y una fila para cada clique máxima , con un coeficiente que es uno en las columnas de vértices que pertenecen al clique y cero en las columnas restantes. Los programas lineales integrales codificados por esta matriz buscan el conjunto independiente de peso máximo del grafo dado, con pesos dados por el vector . ^{[1] [53]} ${\displaystyle A}$ ${\displaystyle c}$

Para una matriz definida de esta manera a partir de un grafo perfecto, los vectores que satisfacen el sistema de desigualdades , forman un politopo integral . Es la envoltura convexa de los vectores indicadores de conjuntos independientes en el grafo, con facetas correspondientes a las camarillas máximas en el grafo. Los grafos perfectos son los únicos grafos para los cuales coinciden los dos politopos definidos de esta manera a partir de conjuntos independientes y de camarillas máximas. ^[53] ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle x\geq 0}$ ${\displaystyle Ax\leq 1}$

Algoritmos

En todos los grafos perfectos, el problema de coloración de grafos , el problema de camarilla máxima y el problema de conjunto independiente máximo pueden resolverse en tiempo polinomial . El algoritmo para el caso general involucra el número de Lovász de estos grafos. El número de Lovász de cualquier grafo puede determinarse etiquetando sus vértices con vectores unitarios de alta dimensión , de modo que cada dos vértices no adyacentes tengan etiquetas perpendiculares y de modo que todos los vectores se encuentren en un cono con un ángulo de apertura lo más pequeño posible. Entonces, el número de Lovász es , donde es el semiángulo de este cono. A pesar de esta definición complicada, se puede calcular un valor numérico preciso del número de Lovász usando programación semidefinida , y para cualquier grafo el número de Lovász está intercalado entre el número cromático y el número de camarilla. Debido a que estos dos números son iguales entre sí en grafos perfectos, también son iguales al número de Lovász. Por lo tanto, se pueden calcular aproximando el número de Lovász con la suficiente precisión y redondeando el resultado al entero más cercano. ^{[54] [55]} ${\displaystyle 1/\cos ^{2}\theta }$ ${\displaystyle \theta }$

El método de solución para programas semidefinidos, utilizado por este algoritmo, se basa en el método del elipsoide para programación lineal . Conduce a un algoritmo de tiempo polinomial para calcular el número cromático y el número de clique en grafos perfectos. Sin embargo, la resolución de estos problemas utilizando el número de Lovász y el método del elipsoide es complicada y tiene un alto exponente polinomial. ^{[54] [55]} Se conocen algoritmos combinatorios más eficientes para muchos casos especiales. ^[56]

Este método también se puede generalizar para encontrar el peso máximo de un grupo, en un gráfico ponderado, en lugar del número de grupos. Un grupo máximo o el peso máximo en sí mismo, y una coloración óptima del gráfico, también se pueden encontrar mediante estos métodos, y un conjunto independiente máximo se puede encontrar aplicando el mismo enfoque al complemento del gráfico. Por ejemplo, un grupo máximo se puede encontrar mediante el siguiente algoritmo: ^[54]

• Recorrer los vértices del gráfico. Para cada vértice , realizar los siguientes pasos: ${\displaystyle v}$
  • Eliminar tentativamente del gráfico. ${\displaystyle v}$
  • Utilice programación semidefinida para determinar el número de camarilla del subgrafo inducido resultante.
  • Si este número de camarilla es el mismo que el de todo el gráfico, eliminar permanentemente ; de ​​lo contrario, restaurar al gráfico. ${\displaystyle v}$ ${\displaystyle v}$
• Devuelve el subgráfico que queda después de todas las eliminaciones permanentes.

El algoritmo para encontrar una coloración óptima es más complicado y depende de la teoría de dualidad de los programas lineales, utilizando este algoritmo de búsqueda de camarillas como un oráculo de separación . ^[54]

Además de resolver estos problemas, otro problema computacional importante relacionado con los grafos perfectos es su reconocimiento, el problema de probar si un grafo dado es perfecto. Durante muchos años, la complejidad de reconocer grafos de Berge y grafos perfectos se consideró por separado (ya que aún no se sabía que fueran equivalentes) y ambos permanecieron abiertos. Se sabía que ambos estaban en co-NP ; para los grafos de Berge, esto se deduce de la definición, ^[57] mientras que para los grafos perfectos se deduce de la caracterización utilizando el producto del número de clique y el número de independencia. ^[6] Después de que se demostró el teorema fuerte del grafo perfecto, Chudnovsky, Cornuéjols, Liu, Seymour y Vušković descubrieron un algoritmo de tiempo polinomial para probar la existencia de agujeros impares o antiagujeros. Por el teorema fuerte del grafo perfecto, esto se puede utilizar para probar si un grafo dado es perfecto, en tiempo polinomial. ^[58]

Conceptos relacionados

Generalizando los grafos perfectos, se dice que una clase de grafos está χ-acotada si el número cromático de los grafos de la clase puede ser acotado por una función de su número de clique. Los grafos perfectos son exactamente los grafos para los cuales esta función es la identidad , tanto para el grafo mismo como para todos sus subgrafos inducidos. ^[59]

La igualdad del número de clique y el número cromático en grafos perfectos ha motivado la definición de otras clases de grafos, en las que otros invariantes de grafos se establecen iguales entre sí. Por ejemplo, los grafos perfectos de dominación se definen como grafos en los que, en cada subgrafo inducido, el conjunto dominante más pequeño (un conjunto de vértices adyacentes a todos los vértices restantes) es igual al tamaño del conjunto independiente más pequeño que es un conjunto dominante. Estos incluyen, por ejemplo, los grafos sin garras . ^[60]

Referencias

1. Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2003). "Progreso en grafos perfectos" (PDF) . Programación matemática . 97 (1-2(B)): 405–422. doi :10.1007/s10107-003-0449-8. MR  2004404. S2CID  5226655. Zbl  1028.05035.
2. Lovász, László (1972). "Hipergrafos normales y la conjetura del grafo perfecto". Matemáticas discretas . 2 (3): 253–267. doi :10.1016/0012-365X(72)90006-4. MR  0302480. Zbl  0239.05111.
3. Cornuéjols, Gérard (2002). "La conjetura del grafo perfecto fuerte". Actas del Congreso Internacional de Matemáticos, vol. III (Beijing, 2002) . Beijing: Higher Education Press. págs. 547–559. arXiv : math/0304464 . MR  1957560. Zbl  1004.05034.
4. Chudnovsky, Maria ; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (2006). "El teorema del grafo perfecto fuerte". Anales de Matemáticas . 164 (1): 51–229. arXiv : math/0212070 . doi :10.4007/annals.2006.164.51. MR  2233847. S2CID  119151552. Zbl  1112.05042.
5. Lovász, László (1972). "Una caracterización de grafos perfectos". Journal of Combinatorial Theory . Serie B. 13 (2): 95–98. doi :10.1016/0095-8956(72)90045-7. MR  0309780. Zbl  0241.05107.
6. Gasparian, GS (junio de 1996). "Gráficos imperfectos mínimos: un enfoque simple". Combinatorica . 16 (2): 209–212. doi :10.1007/bf01844846.
7. Padberg, Manfred W. (diciembre de 1974). "Matrices cero-uno perfectas". Programación matemática . 6 (1): 180–196. doi :10.1007/bf01580235.Para la relación entre el teorema del grafo perfecto fuerte y la caracterización del producto de los grafos perfectos, véanse las observaciones que preceden al teorema 2.1 y que siguen al teorema 2.2.
8. Gallai, Tibor (1958). "Sätze über Graphen máximo-mínimo". Acta Mathematica Academiae Scientiarum Hungaricae . 9 (3–4): 395–434. doi :10.1007/BF02020271. SEÑOR  0124238. S2CID  123953062. Zbl  0084.19603.
9. Bergé, Claude (1961). "Färbung von Graphen deren sämtliche bzw. deren ungerade Kreise starr sind". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe . 10 : 114.
10. Berge, Claude (1963). "Gráficos perfectos". Six Papers on Graph Theory (Seis artículos sobre teoría de grafos ). Calcuta: Indian Statistical Institute. págs. 1–21.
11. Chudnovsky et al. (2003); tenga en cuenta que Chudnovsky et al. definen la capacidad utilizando el complemento de los gráficos utilizados para la definición en la capacidad de Shannon de un gráfico e incluyen un logaritmo que el artículo vinculado no incluye.
12. Hougardy, Stefan (2006). "Clases de grafos perfectos". Matemáticas discretas . 306 (19–20): 2529–2571. doi : 10.1016/j.disc.2006.05.021 . MR  2261918. Zbl  1104.05029.
13. "Los premios DR Fulkerson de 1991 en matemáticas discretas" (PDF) . Destinatarios del premio 1991. Optima: Mathematical Optimization Society Newsletter (35): 4–8. Noviembre de 1991 . Consultado el 21 de enero de 2023 .
14. Mackenzie, Dana (5 de julio de 2002). "Matemáticas: la teoría de grafos descubre las raíces de la perfección". Science . 297 (5578): 38. doi :10.1126/science.297.5578.38. PMID  12098683. S2CID  116891342.
15. "Cita del Premio Fulkerson 2009". Sociedad de Optimización Matemática . Consultado el 21 de enero de 2023 .
16. Chudnovsky, Maria ; Seymour, Paul (2005). "La estructura de los grafos sin garras" (PDF) . Encuestas en combinatoria 2005. Documentos de la 20.ª conferencia combinatoria británica, Universidad de Durham, Durham, Reino Unido, 10-15 de julio de 2005 . Cambridge University Press. págs. 153-171. ISBN 0-521-61523-2. Sr.  2187738. Zbl  1109.05092.
17. "Gráficos bipartitos". Sistema de información sobre clases de grafos y sus inclusiones . Consultado el 24 de enero de 2023 .
18. Kőnig, Dénes (1931). "Gráfok és mátrixok". Matematikai és Fizikai Lapok . 38 : 116-119.
19. Trotter, LE Jr. (1977). "Gráficos de línea perfecta". Programación matemática . 12 (2): 255–259. doi :10.1007/BF01593791. MR  0457293. S2CID  38906333. Zbl  0366.05043.
20. Boros, E. ; Gurvich, V. (2006). "Gráficos perfectos, núcleos y núcleos de juegos cooperativos". Matemáticas discretas . 306 (19–20): 2336–2354. doi :10.1016/j.disc.2005.12.031. MR  2261906. Zbl  1103.05034.
21. Kőnig, Dénes (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre". Annalen Matemáticas . 77 (4): 453–465. doi :10.1007/BF01456961. JFM  46.0146.03. SEÑOR  1511872. S2CID  121097364.
22. Harzheim, Egbert (2005). "Gráficos de comparabilidad". Conjuntos ordenados . Avances en matemáticas. Vol. 7. Nueva York: Springer. págs. 353–368. doi :10.1007/0-387-24222-8_12. ISBN . 0-387-24219-8.MR  2127991.Zbl 1072.06001  .​
23. Berge, Claude (1967). "Algunas clases de grafos perfectos". Graph Theory and Theoretical Physics . Londres: Academic Press. págs. 155-165. MR  0232694. Zbl  0203.26403.
24. Mirsky, Leon (1971). "Un dual del teorema de descomposición de Dilworth". The American Mathematical Monthly . 78 (8): 876–877. doi :10.2307/2316481. JSTOR  2316481. MR  0288054. Zbl  0263.06002.
25. Perfect, Hazel (1980). "Observaciones sobre el teorema de Dilworth en relación con la teoría transversal". Glasgow Mathematical Journal . 21 (1): 19–22. doi : 10.1017/S0017089500003931 . MR  0558270. Zbl  0428.06001.
26. Pnueli, A. ; Lempel, A. ; Even, S. (1971). "Orientación transitiva de grafos e identificación de grafos de permutación". Revista Canadiense de Matemáticas . 23 : 160–175. doi : 10.4153/CJM-1971-016-5 . MR  0292717. Zbl  0204.24604.
27. Kolen, Antoon WJ ; Lenstra, Jan Karel ; Papadimitriou, Christos H .; Spieksma, Frits CR (2007). "Programación de intervalos: una encuesta". Logística de Investigación Naval . 54 (5): 530–543. doi : 10.1002/nav.20231 . SEÑOR  2335544. Zbl  1143.90337.
28. Dagan, Ido; Golumbic, Martin Charles ; Pinter, Ron Yair (1988). "Gráficos trapezoidales y su coloración". Matemáticas Aplicadas Discretas . 21 (1): 35–46. doi :10.1016/0166-218X(88)90032-7. MR  0953414. Zbl  0658.05067.
29. Roberts, Fred S. (1969). "Gráficos de indiferencia". Técnicas de demostración en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) . Nueva York: Academic Press. págs. 139-146. MR  0252267. Zbl  0193.24205.
30. Skrien, Dale J. (1982). "Una relación entre grafos triangulados, grafos de comparabilidad, grafos de intervalos propios, grafos de arco circular propios y grafos de intervalos anidados". Journal of Graph Theory . 6 (3): 309–316. doi :10.1002/jgt.3190060307. MR  0666799. Zbl  0495.05027.
31. Golumbic, Martin Charles (1978). "Gráficos trivialmente perfectos". Matemáticas discretas . 24 (1): 105–107. doi :10.1016/0012-365X(78)90178-4. MR  0522739. Zbl  0384.05057.
32. Hammer, Peter L.; Simeone, Bruno (1981). "La división de un grafo". Combinatorica . 1 (3): 275–284. doi :10.1007/BF02579333. MR  0637832.
33. Prömel, Hans Jürgen; Steger, Angelika (1992). "Casi todos los grafos de Berge son perfectos". Combinatoria, probabilidad y computación . 1 (1): 53–79. doi :10.1017/S0963548300000079. MR  1167295. S2CID  28696495. Zbl  0793.05063.
34. McDiarmid, Colin; Yolov, Nikola (2019). "Gráficos perfectos aleatorios". Estructuras y algoritmos aleatorios . 54 (1): 148–186. arXiv : 1604.00890 . doi :10.1002/rsa.20770. MR  3884617. S2CID  53489550. Zbl  1405.05165.
35. Rose, Donald J. (diciembre de 1970). "Gráficos triangulados y el proceso de eliminación". Revista de análisis matemático y aplicaciones . 32 (3): 597–609. doi :10.1016/0022-247x(70)90282-9.
36. Dirac, Georgia (1961). "Sobre gráficos de circuitos rígidos". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 25 (1–2): 71–76. doi :10.1007/BF02992776. SEÑOR  0130190. S2CID  120608513.
37. Harary, Frank (1974). "Resultados recientes sobre árboles". En Bari, Ruth A. ; Harary, Frank (eds.). Gráficos y combinatoria: actas de la Conferencia Capital sobre teoría de grafos y combinatoria en la Universidad George Washington, 18-22 de junio de 1973 . Lecture Notes in Mathematics. Vol. 406. Springer. págs. 1-9. doi :10.1007/bfb0066429. ISBN 9783540378099.
38. Földes, Stéphane; Hammer, Peter Ladislaw (1977). "Gráficos divididos". Actas de la Octava Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Estatal de Luisiana, Baton Rouge, La., 1977) . Congressus Numerantium. Vol. XIX. Winnipeg: Utilitas Math. págs. 311–315. MR  0505860.
39. Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986). "Gráficos hereditarios de distancia". Revista de teoría combinatoria . Serie B. 41 (2): 182–208. doi :10.1016/0095-8956(86)90043-2. ​​MR  0859310. Zbl  0605.05024.
40. Jung, HA (1978). "Sobre una clase de conjuntos parciales y los gráficos de comparabilidad correspondientes". Journal of Combinatorial Theory, Serie B . 24 (2): 125–133. doi : 10.1016/0095-8956(78)90013-8 . Zbl  0382.05045.
41. Corneil, DG ; Lerchs, H.; Stewart Burlingham, L. (1981). "Gráficos reducibles en complemento". Matemáticas Aplicadas Discretas . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5. MR  0619603. Zbl  0463.05057.
42. Kay, David C.; Chartrand, Gary (1965). "Una caracterización de ciertos grafos ptolemaicos". Revista Canadiense de Matemáticas . 17 : 342–346. doi : 10.4153/CJM-1965-034-0 . MR  0175113. Zbl  0139.17301.
43. Heggernes, Pinar ; Kratsch, Dieter (2007). "Algoritmos de reconocimiento de certificación en tiempo lineal y subgrafos inducidos prohibidos" (PDF) . Nordic Journal of Computing . 14 (1–2): 87–108 (2008). MR  2460558. Zbl  1169.68653.
44. "Gráficos de umbral". Sistema de información sobre clases de grafos y sus inclusiones . Consultado el 12 de febrero de 2023 .
45. Gavril, Fanica (1972). "Algoritmos para coloración mínima, camarilla máxima, cobertura mínima por camarillas y conjunto independiente máximo de un grafo cordal". Revista SIAM de Computación . 1 (2): 180–187. doi :10.1137/0201013.
46. Hammer, Peter L.; Maffray, Frédéric (1990). "Gráficos completamente separables". Matemáticas Aplicadas Discretas . 27 (1–2): 85–99. doi : 10.1016/0166-218x(90)90131-u .
47. Hoáng, CT; Reed, BA (septiembre de 1989). "Algunas clases de grafos perfectamente ordenables". Journal of Graph Theory . 13 (4): 445–463. doi :10.1002/jgt.3190130407.
48. Gyárfás, A.; Lehel, J. (junio de 1988). "Coloración de grafos en línea y por primera vez". Journal of Graph Theory . 12 (2): 217–227. doi :10.1002/jgt.3190120212.
49. Golumbic, Martin Charles ; Trenk, Ann N. (2004). Gráficas de tolerancia . Cambridge Studies in Advanced Mathematics. Vol. 89. Cambridge University Press. doi :10.1017/CBO9780511542985. ISBN . 0-521-82758-2. Sr.  2051713.
50. Hoàng, CT (1987). "Sobre una conjetura de Meyniel". Revista de teoría combinatoria, serie B. 42 ( 3): 302–312. doi :10.1016/0095-8956(87)90047-5. MR  0888682. Zbl  0634.05058.
51. Cicerone, Serafino; Di Stefano, Gabriele (1999). "Clases de grafos entre grafos de paridad y grafos hereditarios de distancia". Matemáticas Aplicadas Discretas . 95 (1–3): 197–216. doi :10.1016/S0166-218X(99)00075-X. MR  1708837. Zbl  0933.05144.
52. Jansen, Klaus (1998). "Una nueva caracterización para grafos de paridad y un problema de coloración con costos". En Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.). LATIN '98: Informática teórica, Tercer Simposio Latinoamericano, Campinas, Brasil, 20-24 de abril de 1998, Actas . Apuntes de clase en Ciencias de la Computación. Vol. 1380. Springer. págs. 249–260. doi :10.1007/BFb0054326. hdl : 11858/00-001M-0000-0014-7BE2-3 . MR  1635464. Zbl  0910.05028.
53. Chvátal, Václav (1975). "Sobre ciertos politopos asociados a grafos". Journal of Combinatorial Theory, Serie B . 18 (2): 138–154. doi :10.1016/0095-8956(75)90041-6. MR  0371732. Zbl  0277.05139.
54. Grötschel, Martin ; Lovász, László ; Schrijver, Alexander (1984). "Algoritmos polinomiales para grafos perfectos". En Berge, C.; Chvátal, V. (eds.). Temas sobre grafos perfectos . Estudios de Matemáticas de Holanda Septentrional. Vol. 88. Holanda Septentrional, Ámsterdam. págs. 325–356. doi :10.1016/S0304-0208(08)72943-8. MR  0778770.
55. Grötschel, Martín ; Lovász, László ; Schrijver, Alejandro (1988). Algoritmos geométricos y optimización combinatoria . Springer-Verlag. SEÑOR  0936633. Zbl  0634.05001.Véase especialmente el capítulo 9, "Conjuntos estables en gráficos", págs. 273-303.
56. Golumbic, Martin Charles (1980). Teoría de grafos algorítmicos y grafos perfectos . Academic Press. doi :10.1016/C2013-0-10739-8. ISBN 0-444-51530-5.Segunda edición, Annals of Discrete Mathematics 57, Elsevier, 2004.
57. Lovász, László (1983). "Gráficos perfectos". En Beineke, Lowell W.; Wilson, Robin J. (eds.). Temas selectos de teoría de grafos, vol. 2. Academic Press. págs. 55–87. ISBN 0-12-086202-6.
58. Chudnovsky, María ; Cornuéjols, Gérard ; Liu, Xinming; Seymour, Pablo ; Vušković, Kristina (2005). "Reconocer gráficos de Berge". Combinatoria . 25 (2): 143–186. doi :10.1007/s00493-005-0012-8. S2CID  2229369.
59. Gyárfás, A. (1987). "Problemas del mundo que rodea a los grafos perfectos" (PDF) . Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985). Zastosowania Matematyki . 19 (3–4): 413–441 (1988). MR  0951359.
60. Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997). "Gráficos sin garras: un estudio". Matemáticas discretas . 164 (1–3): 87–147. doi : 10.1016/S0012-365X(96)00045-3 . MR  1432221.

Enlaces externos

• El teorema del grafo perfecto fuerte de Václav Chvátal .
• Problemas abiertos sobre gráficos perfectos, mantenidos por el Instituto Americano de Matemáticas .
• Problemas perfectos, mantenido por Václav Chvátal.
• Sistema de información sobre inclusiones de clases de grafos: grafo perfecto