Gráfico de linha perfeita - Line perfect graph

Um gráfico de linha perfeita. As arestas em cada componente bicconectado são coloridas em preto se o componente for bipartido, azul se o componente for um tetraedro e vermelho se o componente for um livro de triângulos.

Na teoria dos grafos , um gráfico de linha perfeita é um gráfico cujo gráfico de linha é um gráfico perfeito . Equivalentemente, esses são os gráficos nos quais todo ciclo simples de comprimento ímpar é um triângulo.

Um gráfico é linha perfeita se e somente se cada um de seus componentes bicconectados for um gráfico bipartido , o gráfico completo ou um livro triangular . Como esses três tipos de componentes bicconectados são gráficos perfeitos, cada gráfico de linha perfeita é ele próprio perfeito. Por raciocínio semelhante, todo gráfico de linha perfeita é um gráfico de paridade , um gráfico de Meyniel e um gráfico perfeitamente ordenável . ${\ displaystyle K_ {4}}$ ${\ displaystyle K_ {1,1, n}}$

Os gráficos de linhas perfeitas generalizam os grafos bipartidos e compartilham com eles as propriedades de que a correspondência máxima e a cobertura mínima de vértices têm o mesmo tamanho e que o índice cromático é igual ao grau máximo .

Veja também

• Gráfico estrangulado , um gráfico em que cada ciclo periférico é um triângulo

Referências