En matemáticas de teoría de grafos , un gráfico estrangulado es un gráfico en el que eliminar los bordes de cualquier ciclo inducido de longitud mayor que tres desconectaría el gráfico restante. Es decir, son las gráficas en las que cada ciclo periférico es un triángulo.
En un gráfico plano máximo , o más generalmente en todo gráfico poliédrico , los ciclos periféricos son exactamente las caras de una incrustación plana del gráfico, por lo que un gráfico poliédrico se estrangula si y sólo si todas las caras son triángulos, o de manera equivalente, es máximo. plano. Cada gráfico cordal está estrangulado, porque los únicos ciclos inducidos en los gráficos cordales son triángulos, por lo que ya no hay ciclos que eliminar.
Una suma de camarilla de dos gráficos se forma identificando juntas dos camarillas de igual tamaño en cada gráfico y luego posiblemente eliminando algunos de los bordes de la camarilla. Para la versión de sumas de camarillas relevantes para gráficos estrangulados, se omite el paso de eliminación de bordes. Una suma de camarilla de este tipo entre dos grafos estrangulados da como resultado otro grafo estrangulado, ya que cada ciclo largo inducido en la suma debe estar confinado a un lado o al otro (de lo contrario, tendría una cuerda entre los vértices en los que cruzó desde uno). lado de la suma al otro), y las partes desconectadas de ese lado formado al eliminar el ciclo deben permanecer desconectadas en la suma camarilla. Cada gráfico cordal se puede descomponer de esta manera en una suma camarilla de gráficos planos completos , y cada gráfico plano máximo se puede descomponer en una suma camarilla de gráficos planos máximos conectados por 4 vértices .
Como muestran Seymour y Weaver (1984), estos son los únicos bloques de construcción posibles de gráficos estrangulados: los gráficos estrangulados son exactamente los gráficos que pueden formarse como sumas de camarillas de gráficos completos y gráficos planos máximos.