Gráfica cordal

En la teoría de gráficas, una rama de las matemáticas, una gráfica cordal es aquella en la que todo ciclo de cuatro o más vértices tiene una cuerda, es decir, una arista que no es parte del ciclo pero une a dos vértices en el ciclo. De forma equivalente, una gráfica es cordal si todos sus ciclos inducidos tienen tres vértices. Las gráficas cordales también pueden caracterizarse como las gráficas que tienen órdenes de eliminación perfecta, como las gráficas en las que todo separdor minimal es un clan, y como las gráficas de intersección de los subárboles de un árbol. Aunque estos nombres actualmente están en desuso, las gráficas cordales también son conocidas como gráficas de circuitos rígidos^[1] o gráficas trianguladas;^[2] una compleción cordal de una gráfica también se conoce como una triangulación de la gráfica.

Las gráficas cordales forman un subconjunto de las gráficas perfectas. Pueden ser reconocidas en tiempo lineal (sobre el número de vértices y número de aristas) y varios problemas que son computacionalmente difíciles en el caso general, como coloración por vértices o el problema del clan, se pueden resolver en tiempo polinomial cuando la entrada es cordal^[3] El treewidth de una gráfica arbitraria puede caracterizarse en términos del tamaño de los clanes en las gráficas cordales que la contienen.