Gráfico de línea perfecta

En teoría de grafos , un grafo perfecto por líneas es un grafo cuyo grafo por líneas es un grafo perfecto . De forma equivalente, estos son los grafos en los que cada ciclo simple de longitud impar es un triángulo. ^{[ 1 ]}

Un grafo es perfecto por líneas si y solo si cada uno de sus componentes biconexos es un grafo bipartito , el grafo completo K ₄ , o un libro triangular K _{1,1, n} . ^{[ 2 ]} Debido a que estos tres tipos de componentes biconexos son todos grafos perfectos en sí mismos, todo grafo perfecto por líneas es en sí mismo perfecto. ^{[ 1 ]} Por un razonamiento similar, todo grafo perfecto por líneas es un grafo de paridad , ^{[ 3 ]} un grafo de Meyniel , ^{[ 4 ]} y un grafo perfectamente ordenable .

Los grafos perfectos de línea generalizan los grafos bipartitos y comparten con ellos las propiedades de que el emparejamiento máximo y la cobertura mínima de vértices tienen el mismo tamaño, y que el índice cromático es igual al grado máximo . ^{[ 5 ]}

• Grafo estrangulado , un grafo en el que cada ciclo periférico es un triángulo.