grafico perfecto

Gráfico con estrecha relación de coloración de camarilla

La gráfica del duoprisma 3-3 (la gráfica lineal de ) es perfecta. 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 gráfico perfecto es un gráfico en el que el número cromático es igual al tamaño de la camarilla máxima , tanto en el gráfico mismo como en cada subgrafo inducido . En todos los gráficos, el número cromático es mayor o igual al tamaño de la camarilla máxima, pero pueden estar muy separados. Un gráfico es perfecto cuando estos números son iguales y permanecen iguales después de eliminar subconjuntos arbitrarios de vértices.

Los gráficos perfectos incluyen muchas familias importantes de gráficos y sirven para unificar resultados relacionados con colores y camarillas en esas familias. Por ejemplo, en todos los gráficos perfectos, el problema de coloración de gráficos , el problema de la camarilla máxima y el problema del conjunto independiente máximo se pueden resolver en tiempo polinomial , a pesar de su mayor complejidad para los gráficos no perfectos. Además, varios teoremas minimax importantes en combinatoria , incluido el teorema de Dilworth y el teorema de Mirsky sobre conjuntos parcialmente ordenados , el teorema de Kőnig sobre coincidencias y el teorema de Erdős-Szekeres sobre secuencias monótonas, pueden expresarse en términos de la perfección de ciertos gráficos asociados.

El teorema de la gráfica perfecta establece que la gráfica complementaria de una gráfica perfecta también es perfecta. El fuerte teorema del gráfico perfecto caracteriza los gráficos perfectos en términos de ciertos subgrafos inducidos prohibidos , lo que lleva a un algoritmo de tiempo polinomial para probar si un gráfico es perfecto.

Definiciones y caracterizaciones

Una camarilla en un gráfico no dirigido es un subconjunto de sus vértices que son todos adyacentes entre sí. La coloración de un gráfico asigna un color a cada vértice para que cada dos vértices adyacentes tengan colores diferentes. En particular, a todos los vértices de cualquier camarilla se les deben asignar colores diferentes, por lo que el número cromático (el número mínimo de colores en cualquier coloración) siempre es mayor o igual que el número de camarilla , el número de vértices en la camarilla máxima . Las gráficas perfectas se definen como aquellas gráficas en las que estos dos números son iguales, no sólo en la gráfica misma, sino en cada subgrafo inducido obtenido al eliminar algunos de sus vértices. ^[1]

Dos gráficas perfectas complementarias

El teorema de la gráfica perfecta afirma que la gráfica complementaria de una gráfica perfecta es en sí misma perfecta. El gráfico complementario tiene una arista entre dos vértices si y sólo si el gráfico dado no la tiene. Una camarilla, en el gráfico de complemento, corresponde a un conjunto independiente en lo dado. Una coloración del gráfico de complemento corresponde a una cubierta de camarilla , una partición de los vértices del gráfico dado en camarillas. El hecho de que el complemento de un gráfico 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 claramente, lo mismo ocurre en cada subgrafo inducido del gráfico complementario. Esto proporciona una definición alternativa y equivalente de los gráficos perfectos: son los gráficos para los cuales, en cada subgrafo inducido, el número de independencia es igual al número de cobertura de camarilla. ^[2] ${\displaystyle G}$ ${\displaystyle G}$

Un ciclo de siete vértices y su complemento, que muestra en cada caso una coloración óptima y una camarilla máxima (mostrada con bordes gruesos). Dado que ninguno de los gráficos utiliza una cantidad de colores igual al tamaño de su camarilla, ninguno es perfecto.

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 gráficos de ciclos y sus complementos dentro de un gráfico determinado. Un ciclo de duración impar, mayor que tres, no es perfecto: su número de camarilla es dos, pero su número cromático es tres. Según 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 sólo 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 de la gráfica perfecta fuerte puede enunciarse de manera más sucinta: una gráfica es perfecta si y sólo si no tiene ningún elemento impar. agujero ni algún antiagujero extraño. ^[3]

Estos resultados se pueden combinar en otra caracterización de gráficos perfectos: son los gráficos para los cuales el producto del número de camarilla y el número de independencia es mayor o igual al número de vértices, y para los cuales lo mismo ocurre con todos los subgrafos inducidos. Debido a que el enunciado de esta caracterización permanece invariante bajo complementación de gráficas, implica el teorema de la gráfica perfecta. Una dirección de esta caracterización se desprende fácilmente de la definición original de perfecto: el número de vértices en cualquier gráfico es igual a la suma de los tamaños de las clases de color en una coloración óptima, y ​​es menor o igual al número de colores multiplicado por el número de independencia. En un gráfico 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, ^{[4] [5]} pero también se sigue 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 de la camarilla El número y el número de independencia son uno menos que el número de vértices. ^[6]

Historia

La teoría de los grafos perfectos se desarrolló a partir de un resultado de 1958 de Tibor Gallai que en el lenguaje moderno puede interpretarse como que el complemento de un grafo bipartito es perfecto; ^[7] este resultado también puede verse como un equivalente simple del teorema de Kőnig , un resultado mucho anterior que relaciona coincidencias y coberturas de vértices en gráficos bipartitos. La primera formulación del concepto de gráficas perfectas de manera más general fue en un artículo de 1961 de Claude Berge , en alemán, ^[8] y el primer uso de la frase "gráfica perfecta" parece estar en un artículo de Berge de 1963. ^[9] En estos trabajos unificó el resultado de Gallai con varios resultados similares definiendo gráficas perfectas, y conjeturó tanto el teorema de la gráfica perfecta como el teorema de la gráfica perfecta fuerte. Al formular estos conceptos, Berge se vio motivado por el concepto de capacidad de Shannon de una gráfica , por el hecho de que para gráficas (co)perfectas es igual al número de independencia, y por la búsqueda de ejemplos mínimos de gráficas para las cuales esto no es así. el caso. ^[10] Hasta que se demostró el teorema del gráfico perfecto fuerte, los gráficos descritos por él (es decir, los gráficos sin huecos impares ni antiagujeros impares) se denominaban gráficos de Berge . ^[11]

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. ^[4] 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 . ^[12] El conjeturado teorema de grafos perfectos fuertes se convirtió en el foco de la investigación en la teoría de grafos perfectos durante muchos años, ^[11] hasta que su demostración fue anunciada en 2002 por Maria Chudnovsky , Neil Robertson , Paul Seymour y Robin Thomas , ^{[13 ]} y publicado por ellos en 2006. ^[3] Este trabajo le valió a sus autores el Premio Fulkerson 2009. ^[14] El teorema del grafo perfecto tiene una demostración breve, pero la demostración del teorema del grafo perfecto fuerte es larga y técnica, y se basa en una profunda descomposición estructural de los grafos de Berge. Las técnicas de descomposición relacionadas también han dado sus frutos en el estudio de otras clases de gráficos, y en particular de los gráficos sin garras . ^[15] La caracterización simétrica de gráficos 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. ^[4]

Familias de grafos

Muchas familias de gráficas bien estudiadas son perfectas, ^[11] y en muchos casos el hecho de que estas gráficas sean perfectas corresponde a un teorema minimax para algunos tipos de estructura combinatoria definidas por estas gráficas. Ejemplos de este fenómeno incluyen la perfección de los gráficos bipartitos y sus gráficos lineales , asociados con el teorema de Kőnig que relaciona coincidencias máximas y coberturas de vértices en gráficos bipartitos, y la perfección de los gráficos de comparabilidad , asociados con el teorema de Dilworth y el teorema de Mirsky sobre cadenas y anticadenas en orden parcial. conjuntos . Otras clases importantes de gráficos, definidas por tener una estructura relacionada con los huecos y antiagujeros del teorema del grafo perfecto fuerte, incluyen los gráficos cordales , los gráficos 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 de líneas corresponden a los vértices del gráfico bipartito subyacente y tienen un tamaño igual al grado del vértice correspondiente.

En gráficos bipartitos (con al menos un borde), 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. ^[11] Incluyen como subclases los árboles , gráficos de ciclos de longitud par , gráficos de celosía , gráficos de caballero , gráficos modulares , gráficos de mediana y cubos parciales , entre muchos otros. ^[16] Según el teorema del gráfico perfecto, los conjuntos máximos independientes en gráficos bipartitos tienen el mismo tamaño que sus cubiertas mínimas de camarilla. El conjunto máximo independiente es complementario a una cobertura mínima de vértices , un conjunto de vértices que toca todas las aristas. Una cobertura de camarilla mínima consiste en una coincidencia máxima (tantos bordes separados 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 manera equivalente como una igualdad entre el tamaño de la coincidencia máxima y la cobertura mínima de vértice en gráficos bipartitos, la formulación habitual del teorema de Kőnig . ^{[17] [18]}

Una coincidencia, en cualquier gráfico , es lo mismo que un conjunto independiente en el gráfico lineal , un gráfico que tiene un vértice para cada arista y una arista entre dos vértices para cada par de aristas que comparten un punto final. Los gráficos lineales tienen dos tipos de camarillas: conjuntos de aristas con un punto final común y triángulos en . En los gráficos bipartitos, no hay triángulos, por lo que una cobertura de camarilla corresponde a una cobertura de vértice en . Por lo tanto, en gráficos lineales de gráficos bipartitos, el número de independencia y el número de cobertura de camarilla son iguales. Los subgrafos inducidos de gráficos lineales de gráficos bipartitos son gráficos lineales de subgrafos, por lo que los gráficos lineales de gráficos bipartitos son perfectos. ^[18] Los ejemplos incluyen las gráficas de la torre , las gráficas lineales de las gráficas bipartitas completas . Cada gráfico lineal de un gráfico bipartito es un subgrafo inducido del gráfico de una torre. ^[19] ${\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 gráficos bipartitos son perfectos, su número de camarilla es igual a su número cromático. El número de camarilla del gráfico lineal de un gráfico bipartito es el grado máximo de cualquier vértice del gráfico bipartito subyacente. El número cromático del gráfico lineal de un gráfico bipartito es el índice cromático del gráfico 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 combinación y el índice cromático es el número mínimo de coincidencias necesarias para cubrir todos los bordes. La igualdad de grado máximo e índice cromático, en grafos bipartitos, es otro teorema de Dénes Kőnig . ^[20] En gráficos simples arbitrarios, pueden diferir en uno; este es el teorema de Vizing . ^[18]

Un gráfico lineal perfecto , con componentes bipartitos biconectados negros, libros triangulares azules y rojos ${\displaystyle K_{4}}$

Si un gráfico lineal es perfecto, se dice que el gráfico subyacente es un gráfico lineal perfecto . Las gráficas lineales perfectas son las gráficas cuyos componentes biconectados son las gráficas bipartitas, la gráfica completa , y los libros triangulares , conjuntos de triángulos que comparten una arista. Debido a que estos componentes son perfectos en sí mismos y se combinan de una manera que preserva la propiedad de ser perfectos, cada gráfico lineal perfecto es en sí mismo un gráfico perfecto. ^[18] ${\displaystyle L(G)}$ ${\displaystyle G}$ ${\displaystyle K_{4}}$

Las gráficas bipartitas, sus complementos y las gráficas lineales de las gráficas bipartitas y sus complementos forman cuatro clases básicas de gráficas perfectas que desempeñan un papel clave en la prueba del teorema de la gráfica perfecta fuerte. De acuerdo con la descomposición estructural de gráficos perfectos utilizada como parte de esta prueba, cada gráfico perfecto que aún no se encuentra en una de estas cuatro clases se puede descomponer dividiendo sus vértices en subconjuntos, en una de cuatro formas, denominada unión 2. el complemento de una unión bipartita, un par homogéneo o una partición sesgada . ^[21]

Gráficos de comparabilidad

El 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 , y incomparable de otra manera. 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 un borde 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 finita (y sus gráficos de incomparabilidad complementarios) siempre son 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 según el orden parcial dado. Un conjunto independiente proviene de un subconjunto de elementos de los cuales no hay dos comparables; dicho subconjunto se llama anticadena . Por lo tanto, una coloración de un gráfico de comparabilidad es una partición de sus elementos en anticadenas, y una cubierta de camarilla es una partición de sus elementos en cadenas. El teorema de Dilworth , en la teoría de los ó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 gráficos, esto se puede expresar como: todo gráfico de comparabilidad finita 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 gráfico de comparabilidad finito es perfecto. Estos dos teoremas son equivalentes mediante el 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, siendo el número de anticadenas igual al tamaño de la cadena más grande en general. ^[24] Todo gráfico bipartito es un gráfico de comparabilidad. Por 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]

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

Un gráfico de permutación se define a partir de una permutación sobre una secuencia de elementos totalmente ordenada (convencionalmente, los números enteros desde hasta ), que forman los vértices del gráfico. Los bordes de un gráfico de permutación conectan pares de elementos cuyo orden se invierte mediante la permutación dada. Naturalmente, estos son gráficos de incomparabilidad, para un orden parcial en el que siempre ocurre antes tanto en la secuencia dada como en su permutación. El complemento de un gráfico de permutación es otro gráfico de permutación, para el reverso de la permutación dada. Por tanto, además de ser gráficos de incomparabilidad, los gráficos de permutación son gráficos de comparabilidad. De hecho, las gráficas de permutación son exactamente las gráficas que son a la vez gráficas de comparabilidad e incomparabilidad. ^[26] Una camarilla, en un gráfico 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 son 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 intervalo son gráficos de incomparabilidad de órdenes de intervalo , ordenamientos definidos por conjuntos de intervalos en la línea real siempre que el intervalo esté completamente a la izquierda del intervalo . En el gráfico de intervalo correspondiente, hay un borde desde hasta siempre que los dos intervalos tienen un punto en común. Colorear 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 intervalo 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.

Un gráfico dividido

Un gráfico dividido es un gráfico 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 de la misma manera que un vértice de camarilla no adyacente. Por lo tanto, estos gráficos tienen números de camarilla y números cromáticos iguales y son perfectos. ^[32] Una clase más amplia de gráficos, los gráficos unipolares, se pueden dividir en una camarilla y un gráfico de grupo , una unión disjunta de camarillas. Estos incluyen también los gráficos bipartitos, para los cuales el gráfico de conglomerados es solo una camarilla. Los gráficos unipolares y sus complementos juntos forman la clase de gráficos divididos generalizados . Casi todos los gráficos perfectos son gráficos divididos generalizados, en el sentido de que la fracción de gráficos de vértices perfectos que son gráficos divididos generalizados llega a uno en el límite a medida que crece arbitrariamente. ^[33] ${\displaystyle n}$ ${\displaystyle n}$

Otras propiedades limitantes de casi todos los gráficos perfectos se pueden determinar estudiando los gráficos divididos generalizados. De esta forma, se ha demostrado que casi todas las gráficas perfectas contienen un ciclo hamiltoniano . Si es un gráfico arbitrario, la probabilidad límite que ocurre como un subgrafo inducido de un gráfico perfecto aleatorio grande es 0, 1/2 o 1, respectivamente, ya que no es un gráfico dividido generalizado, es unipolar o counipolar, pero no ambos. o es a la vez unipolar y counipolar. ^[34] ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H}$

Construcciones incrementales

Varias familias de gráficos perfectos se pueden caracterizar mediante una construcción incremental en la que los gráficos de la familia se construyen agregando un vértice a la vez, de acuerdo con ciertas reglas, que garantizan que después de agregar cada vértice el gráfico sigue 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 gráficos cordales también se pueden caracterizar como gráficos que no tienen agujeros (pares o impares). ^[35] Incluyen como casos especiales los bosques, los gráficos de intervalo, ^[36] y los gráficos planos exteriores máximos . ^[37] Las gráficas divididas son exactamente las gráficas que son cordales y tienen un complemento cordal. ^[38] Los k -árboles , fundamentales para la definición de ancho de árbol , son gráficos cordales formados comenzando con una camarilla de ( k + 1) -vértice y agregando repetidamente un vértice para que él y sus vecinos formen una camarilla del mismo tamaño. ^[35]

Tres tipos de suma de vértices en un gráfico hereditario de distancias

• Los gráficos hereditarios de distancia se forman, a partir de un gráfico de un solo vértice, agregando 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 conectado de estos gráficos, las distancias entre los vértices son las mismas que en todo el gráfico. Si solo se utilizan las operaciones gemelas, el resultado es un cografo . ^[39] Los cografos son los gráficos 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 gráficos . ^[41]
• Las gráficas que son tanto cordales como hereditarias por distancias se llaman gráficas ptolemaicas , porque sus distancias obedecen a la desigualdad de Ptolomeo . ^[42] Tienen una forma restringida de la secuencia de construcción hereditaria a distancia, en la que un falso gemelo sólo puede agregarse cuando sus vecinos formen una camarilla. ^[39] Incluyen como casos especiales los gráficos de molino de viento que consisten en camarillas unidas en un solo vértice, y los gráficos de bloques en los que cada componente biconectado es una camarilla. ^[42]
• Los gráficos de umbral se forman a partir de un gráfico vacío agregando 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 gráficos divididos y gráficos trivialmente perfectos. Son exactamente las gráficas que son a la vez trivialmente perfectas y el complemento de una gráfica trivialmente perfecta; también son exactamente las gráficas que son a la vez cografías y gráficas divididas. ^[44]

Si los vértices de un gráfico cordal se colorean en el orden de una secuencia de construcción incremental utilizando un algoritmo de coloración codiciosa , el resultado será una coloración óptima. El orden inverso al orden de los vértices utilizado en esta construcción se denomina orden de eliminación . ^[45] De manera similar, si los vértices de un gráfico 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 gráfico de comparabilidad están coloreados 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 gráficos perfectamente ordenables , gráficos para los cuales existe un ordenamiento que, cuando se restringe a cualquier subgrafo inducido, hace que la coloración codiciosa sea óptima. ^[47] Los cografos son exactamente los gráficos para los cuales todos los ordenamientos de vértices tienen esta propiedad. ^[48]

Otras familias

Se han estudiado muchas otras clases de gráficas perfectas. Por ejemplo, los gráficos fuertemente perfectos son gráficos en los que, en cada subgrafo inducido, existe un conjunto independiente que cruza todas las camarillas máximas . Los gráficos de Meyniel se han llamado muy perfectos porque en ellos cada vértice pertenece a un conjunto independiente. Los gráficos de Meyniel también se pueden definir como los gráficos en los que cada ciclo impar de longitud cinco o más tiene al menos dos cuerdas. ^[49]

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

Un gráfico de paridad se define por la propiedad de que entre cada dos vértices, todos los caminos inducidos tienen la misma paridad: o todos son pares en longitud o todos son impares en longitud. Esto es cierto, por ejemplo, en los gráficos hereditarios de distancia, en los que todos los caminos inducidos entre los mismos dos vértices tienen la misma longitud. ^[50] También es cierto para los gráficos bipartitos: para dos vértices en el mismo lado de una bipartición, todos los caminos tienen una longitud par, y para dos vértices en lados opuestos todos los caminos tienen una longitud impar. Los gráficos de paridad son una subclase de los gráficos de Meyniel: en cualquier ciclo largo e impar de un gráfico de paridad, se necesitan al menos dos cuerdas para evitar que el ciclo se divida en dos caminos inducidos de diferente paridad. El prisma sobre cualquier gráfico de paridad (su producto cartesiano con una sola arista) es otro gráfico de paridad, y los gráficos de paridad son los únicos cuyos prismas son perfectos. ^[51]

Los gráficos de tolerancia se definen especificando tanto un intervalo de la línea real para cada vértice como un número real no negativo , la tolerancia del vértice. Dos vértices son adyacentes siempre que sus intervalos se superpongan en una longitud que sea al menos tan grande como el mínimo de sus dos tolerancias. Por tanto, los gráficos de intervalo son un caso especial de gráficos de tolerancia, que tienen tolerancia cero. Al igual que los gráficos de intervalo, los gráficos de tolerancia se pueden utilizar para modelar problemas de programación, donde las tareas a programar solo pueden compartir recursos durante un corto período de tiempo (la tolerancia de las tareas). Los complementos de los gráficos de tolerancia forman una subclase de los gráficos perfectamente ordenables, por lo que los gráficos de tolerancia son perfectos. ^[52]

Matrices, poliedros y programación entera.

Los gráficos 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 programas enteros se expresan en forma canónica buscando un vector que maximice una función objetivo lineal , sujeto a las restricciones lineales y . Aquí, se da como una matriz , y y se dan como dos vectores. Aunque los programas lineales y los programas enteros se especifican de la misma manera, se diferencian en que, en un programa lineal, se permite que el vector solución tenga números reales arbitrarios como coeficientes, mientras que en un programa entero estos coeficientes desconocidos deben ser números enteros. Esto marca una gran diferencia en la complejidad computacional de estos problemas: la programación lineal se puede resolver en tiempo polinómico , pero la programación entera es NP-difícil . ^[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. Un programa lineal se llama programa lineal integral si una solución óptima del programa entero también es óptima para el programa lineal. (De lo contrario, la relación entre los dos valores de la solución se llama brecha de integralidad y es importante al analizar algoritmos de aproximación para el programa entero). Se pueden usar gráficas perfectas 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 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 máxima de incidencia de camarilla versus vértice de un gráfico perfecto. Esta matriz tiene una columna para cada vértice del gráfico, y una fila para cada camarilla máxima , con un coeficiente que es uno en las columnas de vértices que pertenecen a la camarilla y cero en las columnas restantes. Los programas lineales integrales codificados por esta matriz buscan el conjunto independiente de peso máximo del gráfico dado, con pesos dados por el vector . ^{[1] [53]} ${\displaystyle A}$ ${\displaystyle c}$

Para una matriz definida de esta manera a partir de un gráfico perfecto, el conjunto de vectores que satisfacen el sistema de desigualdades , forman un politopo integral . Es la cáscara convexa de los vectores indicadores de conjuntos independientes en el gráfico, con facetas correspondientes a las camarillas máximas en el gráfico. Los gráficos perfectos son los únicos gráficos 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 gráficos perfectos, el problema de coloración de gráficos , el problema de camarilla máxima y el problema de conjunto independiente máximo se pueden resolver en tiempo polinomial . El algoritmo para el caso general involucra el número de Lovász de estos gráficos. El número de Lovász de cualquier gráfico se puede determinar etiquetando sus vértices mediante 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 complicada definición, se puede calcular un valor numérico preciso del número de Lovász mediante programación semidefinida y, para cualquier gráfico, el número de Lovász se intercala entre el número cromático y el número de camarilla. Como estos dos números son iguales en gráficas perfectas, también son iguales al número de Lovász. Por lo tanto, se pueden calcular aproximando el número de Lovász con 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 camarilla en gráficos perfectos. Sin embargo, resolver estos problemas utilizando el número de Lovász y el método del elipsoide es complicado y tiene un exponente polinómico alto. ^{[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 una camarilla, en un gráfico ponderado, en lugar del número de camarilla. Estos métodos también pueden encontrar una camarilla de peso máxima o máxima y una coloración óptima del gráfico, y se puede encontrar un conjunto máximo independiente aplicando el mismo enfoque al complemento del gráfico. Por ejemplo, se puede encontrar una camarilla máxima mediante el siguiente algoritmo: ^[54]

• Recorre los vértices del gráfico. Para cada vértice , realice los siguientes pasos: ${\displaystyle v}$
  • Quitar provisionalmente 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 para todo el gráfico, elimine permanentemente ; de lo contrario, restablezca el gráfico. ${\displaystyle v}$ ${\displaystyle v}$
• Devuelve el subgrafo 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 la dualidad de los programas lineales, utilizando este algoritmo de búsqueda de camarillas como oráculo de separación . ^[54]

Más allá de resolver estos problemas, otro problema computacional importante relacionado con los gráficos perfectos es su reconocimiento: es decir, dado un gráfico arbitrario, un algoritmo de reconocimiento debe determinar si es un gráfico perfecto o no. Durante muchos años, la complejidad de reconocer los gráficos de Berge y los gráficos 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 gráficos de Berge, esto se desprende de la definición, ^[57] mientras que para los gráficos perfectos se deriva de la caracterización utilizando el producto del número de camarilla y el número de independencia. ^[5] Después de que se demostró el teorema del grafo perfecto fuerte, Chudnovsky, Cornuéjols, Liu, Seymour y Vušković descubrieron un algoritmo de tiempo polinómico para probar la existencia de agujeros impares o antiagujeros. Según el teorema del gráfico perfecto fuerte, esto se puede utilizar para probar si un gráfico dado es perfecto, en tiempo polinomial. ^[58]

Conceptos relacionados

Generalizando los gráficos perfectos, se dice que una clase de gráfico está limitada por χ si el número cromático de los gráficos de la clase puede estar acotado por una función de su número de camarilla. Las gráficas perfectas son exactamente aquellas gráficas para las cuales esta función es la identidad , tanto para la gráfica misma como para todos sus subgrafos inducidos. ^[59]

La igualdad del número de camarilla y el número cromático en gráficos perfectos ha motivado la definición de otras clases de gráficos, en las que otros invariantes de gráficos se igualan entre sí. Por ejemplo, los gráficos de dominación perfecta se definen como gráficos 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. Entre ellos se encuentran, por ejemplo, los gráficos sin garras . ^[60]

Referencias

1. Chudnovsky, María ; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (2003). "Progreso en gráficas perfectas" (PDF) . Programación Matemática . 97 (1-2 (B)): 405–422. doi :10.1007/s10107-003-0449-8. SEÑOR  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. SEÑOR  0302480. Zbl  0239.05111.
3. Chudnovsky, María ; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (2006). "El teorema del gráfico perfecto fuerte". Anales de Matemáticas . 164 (1): 51–229. arXiv : matemáticas/0212070 . doi : 10.4007/annals.2006.164.51. SEÑOR  2233847. S2CID  119151552. Zbl  1112.05042.
4. Lovász, László (1972). "Una caracterización de gráficas perfectas". Revista de teoría combinatoria . Serie B. 13 (2): 95–98. doi :10.1016/0095-8956(72)90045-7. Señor  0309780. Zbl  0241.05107.
5. Gasparian, GS (junio de 1996). "Gráficos mínimos imperfectos: un enfoque simple". Combinatoria . 16 (2): 209–212. doi :10.1007/bf01844846.
6. Padberg, Manfred W. (diciembre de 1974). "Matrices perfectas cero uno". Programación Matemática . 6 (1): 180–196. doi :10.1007/bf01580235.Para conocer la relación entre el teorema de grafos perfectos fuertes y la caracterización del producto de grafos perfectos, véanse los comentarios que preceden al teorema 2.1 y siguen al teorema 2.2.
7. 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.
8. 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.
9. Bergé, Claude (1963). "Gráficos perfectos". Seis artículos sobre teoría de grafos . Calcuta: Instituto de Estadística de la India. págs. 1–21.
10. Chudnovsky y col. (2003); tenga en cuenta que Chudnovsky et al definen la capacidad utilizando el complemento de los gráficos utilizados para la definición en Shannon de la capacidad de un gráfico e incluyen un logaritmo que el artículo vinculado no incluye.
11. Hougardy, Stefan (2006). "Clases de gráficas perfectas". Matemáticas discretas . 306 (19–20): 2529–2571. doi : 10.1016/j.disc.2006.05.021 . SEÑOR  2261918. Zbl  1104.05029.
12. "Premios DR Fulkerson de 1991 en Matemáticas Discretas" (PDF) . Ganadores del premio 1991. Optima: Boletín de la Sociedad de Optimización Matemática (35): 4–8. Noviembre de 1991 . Consultado el 21 de enero de 2023 .
13. Mackenzie, Dana (5 de julio de 2002). "Matemáticas: la teoría de grafos descubre las raíces de la perfección". Ciencia . 297 (5578): 38. doi :10.1126/science.297.5578.38. PMID  12098683. S2CID  116891342.
14. "Mención del Premio Fulkerson 2009". Sociedad de Optimización Matemática . Consultado el 21 de enero de 2023 .
15. Chudnovsky, María ; Seymour, Paul (2005). "La estructura de los gráficos sin garras" (PDF) . Encuestas en combinatoria 2005. Artículos de la vigésima conferencia combinatoria británica, Universidad de Durham, Durham, Reino Unido, 10 al 15 de julio de 2005 . Prensa de la Universidad de Cambridge. págs. 153-171. ISBN 0-521-61523-2. SEÑOR  2187738. Zbl  1109.05092.
16. "Gráficos bipartitos". Sistema de Información sobre Clases de Grafos y sus Inclusiones . Consultado el 24 de enero de 2023 .
17. Kőnig, Dénes (1931). "Gráfok és mátrixok". Matematikai és Fizikai Lapok . 38 : 116-119.
18. Trotter, LE, Jr. (1977). "Gráficos de líneas perfectas". Programación Matemática . 12 (2): 255–259. doi :10.1007/BF01593791. SEÑOR  0457293. S2CID  38906333. Zbl  0366.05043.{{cite journal}}: CS1 maint: multiple names: authors list (link)
19. Boros, E .; Gurvich, V. (2006). "Gráficos, núcleos y núcleos perfectos de juegos cooperativos". Matemáticas discretas . 306 (19–20): 2336–2354. doi :10.1016/j.disc.2005.12.031. SEÑOR  2261906. Zbl  1103.05034.
20. 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.
21. Cornuéjols, Gérard (2002). "La conjetura del grafo perfecto fuerte". Actas del Congreso Internacional de Matemáticos, vol. III (Pekín, 2002) . Beijing: Prensa de educación superior. págs. 547–559. arXiv : matemáticas/0304464 . SEÑOR  1957560. Zbl  1004.05034.
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. Señor  2127991. Zbl  1072.06001.
23. Bergé, Claude (1967). "Algunas clases de gráficas perfectas". Teoría de Grafos y Física Teórica . Londres: Academic Press. págs. 155-165. SEÑOR  0232694. Zbl  0203.26403.
24. Mirsky, León (1971). "Un dual del teorema de descomposición de Dilworth". El Mensual Matemático Estadounidense . 78 (8): 876–877. doi :10.2307/2316481. JSTOR  2316481. SEÑOR  0288054. Zbl  0263.06002.
25. Perfecto, Hazel (1980). "Observaciones sobre el teorema de Dilworth en relación con la teoría transversal". Revista de Matemáticas de Glasgow . 21 (1): 19-22. doi : 10.1017/S0017089500003931 . Señor  0558270. Zbl  0428.06001.
26. Pnueli, A .; Lempel, A .; Incluso, S. (1971). "Orientación transitiva de gráficos e identificación de gráficos de permutación". Revista Canadiense de Matemáticas . 23 : 160-175. doi : 10.4153/CJM-1971-016-5 . Señor  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, Martín Carlos ; Pinter, Ron Yair (1988). "Gráficos trapezoidales y su coloración". Matemática Aplicada Discreta . 21 (1): 35–46. doi :10.1016/0166-218X(88)90032-7. SEÑOR  0953414. Zbl  0658.05067.
29. Roberts, Fred S. (1969). "Gráficos de indiferencia". Técnicas de prueba en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) . Nueva York: Academic Press. págs. 139-146. SEÑOR  0252267. Zbl  0193.24205.
30. Skrien, Dale J. (1982). "Una relación entre gráficos triangulados, gráficos de comparabilidad, gráficos de intervalos adecuados, gráficos de arco circular adecuados y gráficos de intervalos anidados". Revista de teoría de grafos . 6 (3): 309–316. doi :10.1002/jgt.3190060307. SEÑOR  0666799. Zbl  0495.05027.
31. Golumbic, Martín Charles (1978). "Gráficos trivialmente perfectos". Matemáticas discretas . 24 (1): 105-107. doi :10.1016/0012-365X(78)90178-4. SEÑOR  0522739. Zbl  0384.05057.
32. Martillo, Peter L.; Simeone, Bruno (1981). "La escisión de un gráfico". Combinatoria . 1 (3): 275–284. doi :10.1007/BF02579333. SEÑOR  0637832.
33. Prömel, Hans Jürgen; Steger, Angelika (1992). "Casi todos los gráficos de Berge son perfectos". Combinatoria, Probabilidad y Computación . 1 (1): 53–79. doi :10.1017/S0963548300000079. SEÑOR  1167295. S2CID  28696495. Zbl  0793.05063.
34. McDiarmid, Colin; Yolov, Nikola (2019). "Gráficos perfectos aleatorios". Algoritmos y estructuras aleatorias . 54 (1): 148–186. arXiv : 1604.00890 . doi :10.1002/rsa.20770. SEÑOR  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 y Aplicaciones Matemáticas . 32 (3): 597–609. doi :10.1016/0022-247x(70)90282-9.
36. Dirac, GA (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 en á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 al 22 de junio de 1973 . Apuntes de conferencias de matemáticas. vol. 406. Saltador. págs. 1–9. doi :10.1007/bfb0066429. ISBN 9783540378099.
38. Földes, Stéphane; Martillo, Peter Ladislaw (1977). "Dividir gráficos". Actas de la Octava Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Universidad Estatal de Luisiana, Baton Rouge, Luisiana, 1977) . Congreso Numerantium. vol. XIX. Winnipeg: Utilitas Matemáticas. págs. 311–315. SEÑOR  0505860.
39. Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986). "Gráficos distancia-hereditarios". Revista de teoría combinatoria . Serie B. 41 (2): 182–208. doi :10.1016/0095-8956(86)90043-2. SEÑOR  0859310. Zbl  0605.05024.
40. Jung, HA (1978). "Sobre una clase de posets y las correspondientes gráficas de comparabilidad". Revista de teoría combinatoria, serie B. 24 (2): 125-133. doi : 10.1016/0095-8956(78)90013-8 . Zbl  0382.05045.
41. Corneil, director general ; Lerchs, H.; Stewart Burlingham, L. (1981). "Complementar gráficos reducibles". Matemática Aplicada Discreta . 3 (3): 163–174. doi :10.1016/0166-218X(81)90013-5. SEÑOR  0619603. Zbl  0463.05057.
42. Kay, David C.; Chartrand, Gary (1965). "Una caracterización de ciertos gráficos ptolemaicos". Revista Canadiense de Matemáticas . 17 : 342–346. doi : 10.4153/CJM-1965-034-0 . Señor  0175113. Zbl  0139.17301.
43. Heggernes, Pinar ; Kratsch, Dieter (2007). "Algoritmos de reconocimiento de certificación de tiempo lineal y subgrafos inducidos prohibidos" (PDF) . Revista Nórdica de Computación . 14 (1–2): 87–108 (2008). SEÑOR  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 máximo independiente de un gráfico cordal". Revista SIAM de Computación . 1 (2): 180–187. doi :10.1137/0201013.
46. Martillo, Peter L.; Maffray, Frédéric (1990). "Gráficos completamente separables". Matemática Aplicada Discreta . 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 gráficos perfectamente ordenables". Revista de teoría de grafos . 13 (4): 445–463. doi :10.1002/jgt.3190130407.
48. Gyárfás, A.; Lehel, J. (junio de 1988). "Coloración de gráficos en línea y por primera vez". Revista de teoría de grafos . 12 (2): 217–227. doi :10.1002/jgt.3190120212.
49. 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. SEÑOR  0888682. Zbl  0634.05058.
50. Cicerón, Serafino; Di Stéfano, Gabriele (1999). "Clases de gráficos entre gráficos de paridad y hereditarios de distancia". Matemática Aplicada Discreta . 95 (1–3): 197–216. doi :10.1016/S0166-218X(99)00075-X. SEÑOR  1708837. Zbl  0933.05144.
51. Jansen, Klaus (1998). "Una nueva caracterización de gráficos de paridad y un problema de coloración de costes". 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 conferencias sobre informática. vol. 1380. Saltador. págs. 249–260. doi :10.1007/BFb0054326. hdl : 11858/00-001M-0000-0014-7BE2-3 . SEÑOR  1635464. Zbl  0910.05028.
52. Golumbic, Martín Charles ; Trenk, Ann N. (2004). Gráficos de tolerancia . Estudios de Cambridge en Matemáticas Avanzadas. vol. 89. Prensa de la Universidad de Cambridge. doi :10.1017/CBO9780511542985. ISBN 0-521-82758-2. SEÑOR  2051713.
53. Chvátal, Václav (1975). "Sobre ciertos politopos asociados a gráficos". Revista de teoría combinatoria, serie B. 18 (2): 138-154. doi :10.1016/0095-8956(75)90041-6. SEÑOR  0371732. Zbl  0277.05139.
54. Grötschel, Martín ; Lovász, László ; Schrijver, Alejandro (1984). "Algoritmos polinómicos para gráficas perfectas". En Bergé, C.; Chvátal, V. (eds.). Temas sobre gráficas perfectas . Estudios de Matemáticas de Holanda Septentrional. vol. 88. Holanda Septentrional, Ámsterdam. págs. 325–356. doi :10.1016/S0304-0208(08)72943-8. SEÑOR  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, Martín Charles (1980). Teoría algorítmica de grafos y grafos perfectos . Prensa académica. 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 seleccionados en teoría de grafos, vol. 2 . Prensa académica. 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 rodean los gráficos perfectos" (PDF) . Actas de la Conferencia Internacional sobre Análisis Combinatorio y sus Aplicaciones (Pokrzywna, 1985). Zastosowania Matematyki . 19 (3–4): 413–441 (1988). SEÑOR  0951359.
60. Faudree, Ralph ; Flandrin, Evelyne; Ryjáček, Zdeněk (1997). "Gráficos sin garras: una encuesta". Matemáticas discretas . 164 (1–3): 87–147. doi : 10.1016/S0012-365X(96)00045-3 . SEÑOR  1432221.

enlaces externos

• El teorema del grafo perfecto fuerte de Václav Chvátal .
• Problemas abiertos sobre gráficas perfectas, 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 gráficos: gráfico perfecto