Cliques, conjuntos independientes y recubrimientos por vértices

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Cliques, conjuntos independientes y recubrimientos por vértices

Tres de las preguntas más estudiadas de la teoría de grafos tratan sobre conjuntos de vértices, y cada una puede enunciarse en una línea.

• Un clique es un conjunto de vértices en el que cada dos son adyacentes. Un clique con k vértices es una copia del grafo completo Kk dentro del grafo. El tamaño del clique más grande es el número de clique, que se escribe ω(G).
• Un conjunto independiente, también llamado conjunto estable, es un conjunto de vértices en el que no hay dos adyacentes. El tamaño del más grande es el número de independencia, α(G).
• Un recubrimiento por vértices es un conjunto de vértices que toca todas las aristas: cada arista tiene al menos un extremo en el conjunto. El tamaño del más pequeño es el número de recubrimiento por vértices, τ(G).

Un clique y un conjunto independiente son opuestos: uno pide todas las aristas posibles entre los vértices elegidos y el otro ninguna. En una red de amistades, un clique es un grupo en el que todos se conocen entre sí, y un conjunto independiente es un grupo de desconocidos mutuos. La palabra «clique» llegó a la materia desde la sociología, donde Luce y Perry la usaron en 1949 precisamente para esos grupos. La guía de vértices y aristas cubre el vocabulario en el que se apoyan estas definiciones.

Cada pregunta esconde una trampa en su enunciado. Un conjunto es maximal cuando no se le puede añadir nada (o, en el caso de un recubrimiento, quitar nada) sin romper la propiedad. Es máximo cuando no existe ningún conjunto más grande con la propiedad (o, en el caso de un recubrimiento, ninguno más pequeño). Todo conjunto máximo es maximal, pero no al revés, y la diferencia entre ambos es donde fallan la mayoría de los algoritmos.

2. Un grafo, tres respuestas, una identidad

El ejemplo que nos acompaña tiene 8 vértices y 12 aristas. Los vértices A, B, C y D están todos unidos entre sí, D, E y F forman un triángulo, y un ciclo de 5 vértices C, D, F, G, H recorre la parte inferior:

E = {AB, AC, AD, BC, BD, CD, CH, DE, DF, EF, FG, GH}      8 vértices, 12 aristas

deg:   A 3   B 3   C 4   D 5   E 2   F 3   G 2   H 2

El clique más grande es {A, B, C, D}, así que ω = 4, y es el único clique de ese tamaño. Los conjuntos independientes más grandes tienen 3 vértices, por ejemplo {A, E, G}, así que α = 3; hay siete. Los recubrimientos por vértices más pequeños tienen 5 vértices, por ejemplo {B, C, D, F, H}, así que τ = 5, y de nuevo hay siete. Los dos sietes no son una coincidencia.

Dos argumentos breves enlazan los tres números. Primero, el complemento de un grafo tiene una arista exactamente donde el grafo no la tiene, así que un clique en G es un conjunto independiente en el complemento y viceversa: ω(G) es igual a α del complemento. Segundo, un conjunto S es independiente exactamente cuando los vértices restantes forman un recubrimiento por vértices. Si alguna arista no tocara los vértices restantes, sus dos extremos estarían en S, así que S no sería independiente, y el argumento funciona igual en sentido inverso. Tomar el S más grande da el recubrimiento más pequeño:

α(G) + τ(G) = n, para todo grafo con n vértices.

Esta identidad suele atribuirse a Gallai, que la publicó en 1959. En el ejemplo, 3 + 5 = 8, y los siete conjuntos independientes más grandes son exactamente los complementos de los siete recubrimientos más pequeños. La consecuencia práctica es que los tres problemas son un único problema con tres disfraces: un algoritmo para cualquiera de ellos, aplicado al grafo o a su complemento, resuelve exactamente los otros dos.

3. Maximal no es máximo

El triángulo {D, E, F} es un clique, y no se le puede añadir ningún vértice, porque ningún otro vértice es adyacente a la vez a D, E y F. Es un clique maximal de tamaño 3, mientras que el máximo es 4. Las aristas CH, FG y GH también son cliques maximales, de tamaño 2: ninguna está en un triángulo. En total, el ejemplo tiene cinco cliques maximales, y solo uno de ellos es máximo.

Los conjuntos independientes caen en la misma trampa con más facilidad. El método voraz natural recorre los vértices y toma cada uno cuyos vecinos aún no se hayan tomado. El resultado siempre es maximal, pero su tamaño depende del orden. Empieza por D, el vértice de mayor grado, y D bloquea cinco vértices de golpe; una vez tomado G, todos los vértices restantes son adyacentes a uno de los dos, y el método se detiene en {D, G}, uno por debajo del óptimo. El ejemplo tiene diez conjuntos independientes maximales, tres de tamaño 2 y siete de tamaño 3. Empezar por los vértices de grado bajo, que bloquean a pocos otros, es una costumbre mejor, pero ningún orden voraz es correcto para todos los grafos.

La lección se traslada al software. Una rutina que «encuentra un clique» o «encuentra un conjunto independiente» suele devolver uno maximal, y rápido. Encontrar uno máximo es una tarea distinta y mucho más difícil, y el resto de este artículo trata de cómo hacerlo, cómo aproximarlo y cómo acotarlo.

4. Listar todos los cliques maximales: Bron–Kerbosch

La forma clásica de encontrar todos los cliques maximales es el algoritmo que Bron y Kerbosch publicaron en 1973. Hace crecer un clique R vértice a vértice y mantiene dos conjuntos más: P, los vértices que aún podrían añadirse porque son adyacentes a todo lo que hay en R, y X, los vértices que podrían añadirse pero ya se exploraron, de modo que cualquier clique que los use ya se ha listado. Cuando P y X están ambos vacíos, R no puede crecer y no se omitió nada, así que R es un clique maximal.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def bron_kerbosch(R, P, X, adj, out):
    """Reporta cada clique maximal que contiene R, usa solo P y evita X."""
    if not P and not X:
        out.append(sorted(R))                 # no se puede añadir nada: R es maximal
        return
    pivot = max(P | X, key=lambda u: len(P & adj[u]))
    for v in sorted(P - adj[pivot]):          # los vecinos del pivote se prueban después
        bron_kerbosch(R | {v}, P & adj[v], X & adj[v], adj, out)
        P.remove(v)
        X.add(v)                              # ya se han reportado todos los cliques con v

def maximal_cliques(adj):
    out = []
    bron_kerbosch(set(), set(adj), set(), adj, out)
    return sorted(out, key=lambda c: (-len(c), c))

def complement(adj):
    return {v: set(adj) - adj[v] - {v} for v in adj}

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(maximal_cliques(G))
# [['A', 'B', 'C', 'D'], ['D', 'E', 'F'], ['C', 'H'], ['F', 'G'], ['G', 'H']]
print(maximal_cliques(complement(G)))   # los conjuntos independientes maximales de G
# [['A', 'E', 'G'], ['A', 'E', 'H'], ['A', 'F', 'H'], ['B', 'E', 'G'], ['B', 'E', 'H'], ['B', 'F', 'H'], ['C', 'E', 'G'], ['C', 'F'], ['D', 'G'], ['D', 'H']]

El pivote es lo que lo hace rápido. Todo clique maximal debe contener el pivote o un vértice no adyacente a él, así que el bucle solo necesita ramificar sobre los no vecinos del pivote; elegir como pivote el vértice de P o X con más vecinos en P ahorra el máximo trabajo. Tomita, Tanaka y Takahashi demostraron en 2006 que con esta regla el tiempo de ejecución es O(3n/3), y esa cota no se puede mejorar, porque Moon y Moser demostraron en 1965 que un grafo con n vértices puede tener 3n/3 cliques maximales cuando n es múltiplo de 3. El grafo extremo es el complemento de n/3 triángulos disjuntos: con 9 vértices tiene 27 cliques maximales, y con 30 vértices tiene 59.049.

La primera línea de la salida lista los cinco cliques maximales de la sección 3, del más grande al más pequeño. La segunda línea ejecuta la misma función sobre el complemento y lista así los diez conjuntos independientes maximales. La función se comprobó frente al buscador de cliques de networkx, que usa el mismo algoritmo, en 3000 grafos aleatorios de hasta 10 vértices.

5. Encontrar exactamente el conjunto independiente más grande

Listar todos los conjuntos maximales suele ser más de lo necesario, y la respuesta puede encontrarse con una búsqueda directa. Dos reglas bastan para un método correcto. Un vértice de grado 0 siempre se puede tomar. Un vértice v de grado 1 también se puede tomar siempre: si un conjunto independiente más grande contiene a su único vecino u, cambiar u por v lo mantiene independiente y del mismo tamaño. Cuando no se aplica ninguna de las dos reglas, elige un vértice y prueba ambas posibilidades: tomarlo y borrar sus vecinos, o dejarlo fuera.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def remove(adj, gone):
    return {u: adj[u] - gone for u in adj if u not in gone}

def greedy_independent_set(adj, order):
    """Toma cada vértice por turno salvo que ya se haya tomado un vecino. Siempre maximal."""
    chosen = set()
    for v in order:
        if not adj[v] & chosen:
            chosen.add(v)
    return chosen

def max_independent_set(adj):
    """Exacto: un vértice de grado 0 o 1 siempre se puede tomar sin riesgo; si no, ramifica."""
    if not adj:
        return set()
    v = min(adj, key=lambda u: len(adj[u]))
    if len(adj[v]) <= 1:
        return {v} | max_independent_set(remove(adj, {v} | adj[v]))
    v = max(adj, key=lambda u: len(adj[u]))
    take = {v} | max_independent_set(remove(adj, {v} | adj[v]))   # v dentro, vecinos fuera
    skip = max_independent_set(remove(adj, {v}))                  # v fuera
    return take if len(take) >= len(skip) else skip

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(sorted(greedy_independent_set(G, 'DGABCEFH')))   # empieza por el vértice de mayor grado
# ['D', 'G']
best = max_independent_set(G)
print(sorted(best), sorted(set(G) - best))             # conjunto independiente más grande, recubrimiento más pequeño
# ['A', 'E', 'G'] ['B', 'C', 'D', 'F', 'H']

La primera línea repite el callejón sin salida voraz de la sección 3. La segunda da un conjunto independiente más grande, {A, E, G}, y por la identidad de la sección 2, los vértices que deja fuera forman un recubrimiento por vértices más pequeño, {B, C, D, F, H}. La función se comprobó frente a networkx en los mismos 3000 grafos aleatorios, y cada conjunto que devolvió era independiente y del tamaño correcto.

Ramificar sobre un vértice de grado máximo es deliberado: tomarlo borra el mayor número de vértices, así que esa rama reduce el grafo más deprisa. Las reglas de grado también hacen que la búsqueda nunca ramifique en un bosque, ya que todo bosque tiene un vértice de grado 0 o 1, y borrar vértices lo mantiene como bosque. En grafos generales la búsqueda sigue siendo exponencial, pero mucho menor que los 2n subconjuntos: Tarjan y Trojanowski refinaron reglas de este tipo en 1977 hasta obtener un algoritmo O(2n/3), y trabajos posteriores han reducido aún más la base.

6. Recubrimiento por vértices: una 2-aproximación y un test exacto rápido

El recubrimiento por vértices tiene dos propiedades de las que carecen sus compañeros, y ambas surgen de mirar las aristas. La primera es una aproximación sencilla. Recorre las aristas y, cada vez que una arista no tenga todavía ningún extremo en el recubrimiento, añade sus dos extremos. Las aristas elegidas así no comparten ningún vértice, de modo que forman un emparejamiento, y ninguna otra arista podría sumarse a ellas, así que es un emparejamiento maximal. Cualquier recubrimiento debe contener al menos un extremo de cada arista del emparejamiento, y esos extremos son todos distintos, así que τ es al menos el número de aristas del emparejamiento. El método toma exactamente dos vértices por arista del emparejamiento, así que su recubrimiento nunca supera el doble del óptimo. Este argumento suele atribuirse a Gavril y a Yannakakis, y el libro de Garey y Johnson de 1979 lo dio a conocer ampliamente.

def matching_cover(edges):
    """2-aproximación: toma ambos extremos de cada arista que aún no esté cubierta."""
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}                   # estas aristas forman un emparejamiento maximal
    return cover

def cover_of_size(edges, k):
    """Un recubrimiento por vértices con k vértices como mucho, o None. Como mucho 2^k ramas."""
    if not edges:
        return set()
    if k == 0:
        return None
    u, v = edges[0]                           # u o v debe estar en cualquier recubrimiento
    for w in (u, v):
        rest = [e for e in edges if w not in e]
        found = cover_of_size(rest, k - 1)
        if found is not None:
            return found | {w}
    return None

E = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH']

print(sorted(matching_cover(E)))
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
print(cover_of_size(E, 4))
# None
print(sorted(cover_of_size(E, 5)))
# ['A', 'B', 'D', 'F', 'H']

En el ejemplo el emparejamiento es AB, CD, EF y GH, y el método toma los ocho vértices. Es un mal recubrimiento, pero el emparejamiento también demuestra que ningún recubrimiento tiene menos de cuatro vértices, así que el método sabe que su propia respuesta está dentro de un factor 2 sin conocer el óptimo. Una alternativa tentadora, tomar repetidamente el vértice de mayor grado, no tiene esa garantía: en grafos construidos con cuidado, su recubrimiento puede ser peor que el óptimo por un factor que crece con el tamaño del grafo.

La segunda propiedad es que los recubrimientos pequeños son fáciles de encontrar exactamente. Toda arista uv debe tener u o v en el recubrimiento, así que la función cover_of_size prueba ambos y continúa con un presupuesto de k − 1. El árbol de búsqueda tiene profundidad como mucho k y como mucho 2k hojas, sea cual sea el número de vértices. En el ejemplo informa de que no existe ningún recubrimiento de 4 vértices y encuentra uno de 5. Con k = 20, el árbol tiene como mucho alrededor de un millón de hojas, por grande que sea el grafo: el tamaño de la búsqueda depende del tamaño del recubrimiento, no del número de vértices. Los problemas con este comportamiento se llaman tratables con parámetro fijo.

Una regla de preprocesamiento del artículo de Buss y Goldsmith de 1993 reduce primero la entrada. Un vértice con más de k vecinos debe estar en todo recubrimiento de tamaño k, porque de lo contrario harían falta todos sus vecinos. Tras tomar esos vértices, cada vértice restante cubre como mucho k aristas, así que si quedan más de k2 aristas, la respuesta es no. El mejor algoritmo exacto conocido, de Chen, Kanj y Xia en 2010, se ejecuta en tiempo O(1,2738k + kn).

7. ¿Cuán difíciles son estos problemas?

Decidir si un grafo tiene un clique de tamaño k es NP-completo, y también lo es decidir si tiene un recubrimiento por vértices de tamaño k. Ambos estaban en la lista de Karp de 1972 con 21 problemas NP-completos, y el conjunto independiente se deduce de cualquiera de ellos mediante las identidades de la sección 2. No se conoce ningún algoritmo de tiempo polinómico para ninguno de ellos, y encontrar uno demostraría que P = NP.

Las identidades conservan las respuestas exactas pero no las aproximadas, y aquí los tres problemas se separan. El recubrimiento por vértices se puede aproximar dentro de un factor 2, como mostró la sección 6. El clique y el conjunto independiente prácticamente no se pueden aproximar en absoluto: Håstad demostró en 1999 que, para todo ε > 0, ningún algoritmo de tiempo polinómico aproxima el clique más grande dentro de un factor n1−ε salvo que NP = ZPP, y Zuckerman demostró en 2007 que lo mismo se cumple suponiendo solo P ≠ NP. Un pequeño cálculo muestra por qué la identidad no transfiere la garantía: en un grafo con 1000 vértices y τ = 500, un recubrimiento de 1000 vértices está dentro de un factor 2, y sin embargo el conjunto independiente que deja es vacío.

Incluso el factor 2 del recubrimiento por vértices puede ser el final del camino. Dinur y Safra demostraron en 2005 que aproximarlo dentro de un factor 1,36 es NP-difícil, y Khot y Regev demostraron en 2008 que un factor 2 − ε es difícil si la Conjetura de los Juegos Únicos es cierta. El panorama parametrizado también es distinto. El recubrimiento por vértices es tratable con parámetro fijo, como mostró la sección 6, mientras que encontrar un clique de tamaño k es completo para la clase W[1], como demostraron Downey y Fellows en 1995, lo que es una fuerte evidencia de que ningún algoritmo con tiempo de ejecución f(k) · nc existe para él.

8. Cotas que puedes comprobar a mano

Como los números exactos son difíciles de calcular, las cotas sencillas son valiosas, y varias relacionan estos problemas con la coloración y los grados.

• Los cliques fuerzan colores. Los vértices de un clique son adyacentes dos a dos, así que cada uno necesita su propio color: χ(G) ≥ ω(G), donde χ es el número cromático de la guía de coloración de grafos. En el ejemplo el clique {A, B, C, D} obliga a usar 4 colores, y 4 bastan.
• Los colores dan conjuntos independientes. Cada clase de color de una coloración propia es un conjunto independiente, así que los n vértices se reparten en χ conjuntos independientes y el más grande tiene al menos n / χ vértices: α(G) ≥ n / χ(G). En el ejemplo eso da α ≥ 2.
• Los grados bajos dan conjuntos independientes. La cota de Caro–Wei, hallada de forma independiente por Caro en 1979 y por Wei en 1981, afirma que α(G) ≥ ∑ 1 / (d(v) + 1). Coloca los vértices en un orden aleatorio y quédate con cada vértice que aparezca antes que todos sus vecinos: el conjunto resultante es independiente, y cada vértice se conserva con probabilidad 1 / (d(v) + 1). Para el ejemplo la suma es 127/60 ≈ 2,12, y como α es un número entero, α ≥ 3, que aquí es exacto. La guía de grado de un vértice explica por qué estas sumas de grados son tan útiles.
• Muchas aristas fuerzan cliques. El teorema de Turán de 1941 dice que un grafo con n vértices sin ningún clique de tamaño r + 1 tiene como mucho (1 − 1/r) n2 / 2 aristas, y el máximo se alcanza repartiendo los vértices en r grupos casi iguales y uniendo cada par de vértices de grupos distintos. Para r = 2 esto es el teorema de Mantel de 1907: un grafo sin triángulos tiene como mucho n2 / 4 aristas. Con 8 vértices, cualquier grafo con más de 16 aristas contiene un triángulo y cualquier grafo con más de 21 aristas contiene K4.

9. Teoría de Ramsey: el orden es inevitable

El teorema de Turán dice que los grafos densos contienen cliques grandes. La teoría de Ramsey dice algo más fuerte: todo grafo grande contiene un clique grande o un conjunto independiente grande, sea cual sea su densidad. El número de Ramsey R(s, t) es el menor n tal que todo grafo con n vértices tiene un clique de tamaño s o un conjunto independiente de tamaño t. Ramsey demostró en 1930 que estos números existen.

El caso más pequeño es el problema de la fiesta: entre seis personas cualesquiera hay tres amigos mutuos o tres desconocidos mutuos, así que R(3, 3) = 6. La demostración cabe en unas pocas líneas. Elige una persona cualquiera v. De las otras cinco, al menos tres son amigos de v o al menos tres son desconocidos para v; digamos tres amigos x, y y z. Si dos cualesquiera de ellos son amigos, forman un trío de amigos con v. Si ninguno lo es, x, y y z son tres desconocidos entre sí. Cinco personas no bastan: colócalas en un pentágono, haz amigos a los vecinos y desconocidos a todos los demás, y no aparece ningún trío de ninguno de los dos tipos. Una comprobación por fuerza bruta de las 32.768 formas de marcar los 15 pares de seis personas como amigos o desconocidos confirma el resultado.

Más allá de los casos más pequeños, los números de Ramsey son notoriamente difíciles. Greenwood y Gleason hallaron R(4, 4) = 18 en 1955. Para R(5, 5), Exoo demostró en 1989 que es al menos 43, y Angeltveit y McKay demostraron en 2024 que es como mucho 46, tras décadas de cálculo; el valor exacto sigue sin conocerse. Para un k general, Erdős y Szekeres demostraron en 1935 que R(k, k) es menor que 4k, y Erdős demostró en 1947 que es mayor que 2k/2 mostrando que un grafo aleatorio no suele tener ni un clique grande ni un conjunto independiente grande, uno de los primeros usos del método probabilístico. Trabajos posteriores recortaron la cota superior, pero la base 4 se mantuvo hasta que Campos, Griffiths, Morris y Sahasrabudhe la bajaron a (4 − ε)k en un artículo publicado por primera vez en 2023.

10. Grafos especiales en los que los problemas se vuelven fáciles

La NP-dificultad es una afirmación sobre todos los grafos. Muchas clases de grafos que aparecen en la práctica tienen una estructura que hace tratables estos problemas.

• Grafos bipartitos. El teorema de Kőnig de 1931 dice que en un grafo bipartito el recubrimiento por vértices más pequeño tiene exactamente tantos vértices como el emparejamiento más grande, y los emparejamientos más grandes pueden encontrarse en tiempo polinómico con los métodos de flujo de la guía de flujo máximo. El conjunto independiente más grande se obtiene entonces de α = n − τ. La guía de grafos bipartitos desarrolla un ejemplo.
• Árboles y bosques. Las reglas de grado de la sección 5 resuelven cualquier bosque sin ramificar, lo que da un algoritmo de tiempo lineal con las estructuras de datos adecuadas.
• Grafos cordales. Gavril demostró en 1972 que el clique más grande, el conjunto independiente más grande y una coloración óptima de un grafo cordal pueden encontrarse en tiempo polinómico a partir de un orden de eliminación perfecto, como se describe en la guía de grafos cordales.
• Grafos perfectos. En un grafo perfecto, el número cromático es igual al número de clique en todo subgrafo inducido. Grötschel, Lovász y Schrijver demostraron en 1981 que el número de clique y el número de independencia de un grafo perfecto pueden calcularse en tiempo polinómico, usando el método del elipsoide.
• Grafos planos. Un grafo plano no contiene ningún K5, así que su clique más grande tiene como mucho 4 vértices y puede encontrarse comprobando cada conjunto de 4 vértices como mucho. Sin embargo, el conjunto independiente y el recubrimiento por vértices siguen siendo NP-completos: Garey, Johnson y Stockmeyer lo demostraron para grafos planos en 1976, y Garey y Johnson lo extendieron en 1977 a grafos planos con grado máximo 3.

11. Dónde se usan los cliques, los conjuntos independientes y los recubrimientos

• Planificación y conflictos. En un grafo de conflictos, donde se unen las tareas que no pueden compartir una franja horaria, un conjunto independiente es un grupo de tareas que pueden ejecutarse a la vez, y un clique es un grupo que necesita tantas franjas como miembros tiene. Por eso el número de clique es una cota inferior del número de franjas.
• Redes sociales y biológicas. Los cliques modelan grupos de personas muy unidos y complejos de proteínas. Los datos reales tienen ruido, así que los analistas suelen usar versiones relajadas como los k-núcleos de la guía de grado de un vértice, y Bron–Kerbosch sigue siendo la herramienta estándar para listar cliques exactos en redes dispersas.
• Monitorización. Colocar sensores en el menor número de nodos para vigilar todos los enlaces de una red es un problema de recubrimiento por vértices, igual que elegir el menor número de vigilantes en las esquinas para que cada calle quede a la vista de alguno.
• Teoría de códigos. Un conjunto de palabras de código con distancia mínima d es un conjunto independiente en el grafo que une cada dos palabras a distancia menor que d, así que los mejores códigos de una longitud dada son conjuntos independientes de tamaño máximo.
• Comparación de estructuras. Barrow y Burstall observaron en 1976 que la mayor subestructura común de dos grafos, usada para comparar moléculas, corresponde al clique más grande de un grafo producto construido a partir del par. La guía de isomorfismo de grafos trata el problema relacionado de decidir si dos grafos son el mismo.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Mantel, W. (1907). "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)." Wiskundige Opgaven 10, 60 a 61.
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30, 264 a 286.
3. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 a 119.
4. Erdős, P. y Szekeres, G. (1935). "A Combinatorial Problem in Geometry." Compositio Mathematica 2, 463 a 470.
5. Turán, P. (1941). "Egy gráfelméleti szélsőértékfeladatról." Matematikai és Fizikai Lapok 48, 436 a 452.
6. Erdős, P. (1947). "Some Remarks on the Theory of Graphs." Bulletin of the American Mathematical Society 53, 292 a 294.
7. Luce, R. D. y Perry, A. D. (1949). "A Method of Matrix Analysis of Group Structure." Psychometrika 14(2), 95 a 116.
8. Greenwood, R. E. y Gleason, A. M. (1955). "Combinatorial Relations and Chromatic Graphs." Canadian Journal of Mathematics 7, 1 a 7.
9. Gallai, T. (1959). "Über extreme Punkt- und Kantenmengen." Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica 2, 133 a 138.
10. Moon, J. W. y Moser, L. (1965). "On Cliques in Graphs." Israel Journal of Mathematics 3, 23 a 28.
11. Gavril, F. (1972). "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph." SIAM Journal on Computing 1(2), 180 a 187.
12. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." En Complexity of Computer Computations, editado por R. E. Miller y J. W. Thatcher, 85 a 103. New York: Plenum.
13. Bron, C. y Kerbosch, J. (1973). "Algorithm 457: Finding All Cliques of an Undirected Graph." Communications of the ACM 16(9), 575 a 577.
14. Barrow, H. G. y Burstall, R. M. (1976). "Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques." Information Processing Letters 4(4), 83 a 84.
15. Garey, M. R., Johnson, D. S. y Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3), 237 a 267.
16. Garey, M. R. y Johnson, D. S. (1977). "The Rectilinear Steiner Tree Problem is NP-Complete." SIAM Journal on Applied Mathematics 32(4), 826 a 834. Recubrimiento por vértices en grafos planos de grado máximo 3.
17. Tarjan, R. E. y Trojanowski, A. E. (1977). "Finding a Maximum Independent Set." SIAM Journal on Computing 6(3), 537 a 546.
18. Caro, Y. (1979). "New Results on the Independence Number." Informe técnico, Universidad de Tel Aviv.
19. Garey, M. R. y Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman. La 2-aproximación para el recubrimiento por vértices.
20. Wei, V. K. (1981). "A Lower Bound on the Stability Number of a Simple Graph." Memorando técnico de Bell Laboratories 81-11217-9.
21. Grötschel, M., Lovász, L. y Schrijver, A. (1981). "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1(2), 169 a 197.
22. Exoo, G. (1989). "A Lower Bound for R(5, 5)." Journal of Graph Theory 13(1), 97 a 98.
23. Buss, J. F. y Goldsmith, J. (1993). "Nondeterminism within P." SIAM Journal on Computing 22(3), 560 a 572.
24. Downey, R. G. y Fellows, M. R. (1995). "Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]." Theoretical Computer Science 141, 109 a 131.
25. Håstad, J. (1999). "Clique is Hard to Approximate within n^1−ε." Acta Mathematica 182(1), 105 a 142.
26. Dinur, I. y Safra, S. (2005). "On the Hardness of Approximating Minimum Vertex Cover." Annals of Mathematics 162(1), 439 a 485.
27. Tomita, E., Tanaka, A. y Takahashi, H. (2006). "The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments." Theoretical Computer Science 363(1), 28 a 42.
28. Zuckerman, D. (2007). "Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number." Theory of Computing 3, 103 a 128.
29. Khot, S. y Regev, O. (2008). "Vertex Cover Might Be Hard to Approximate to within 2 − ε." Journal of Computer and System Sciences 74(3), 335 a 349.
30. Chen, J., Kanj, I. A. y Xia, G. (2010). "Improved Upper Bounds for Vertex Cover." Theoretical Computer Science 411(40–42), 3736 a 3756.
31. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.
32. Angeltveit, V. y McKay, B. D. (2024). "R(5, 5) ≤ 46." arXiv:2409.15709.
33. Campos, M., Griffiths, S., Morris, R. y Sahasrabudhe, J. (2026). "An Exponential Improvement for Diagonal Ramsey." Annals of Mathematics 203(3), 869 a 932. Publicado por primera vez en 2023 como arXiv:2303.09521.