Mükemmel çizgi grafiği - Line perfect graph

Kusursuz bir çizgi grafiği. Her iki bağlantılı bileşenin kenarları, bileşen iki parçalıysa siyah, bileşen bir tetrahedron ise mavi ve bileşen bir üçgenler kitabıysa kırmızıdır.

İçinde grafik teorisi, bir mükemmel çizgi grafiği bir grafiktir çizgi grafiği bir mükemmel grafik. Eşdeğer olarak, bunlar her tek uzunlukta olan grafiklerdir. basit döngü bir üçgendir.^[1]

Bir grafik, ancak ve ancak her biri çift ​​bağlantılı bileşenler bir iki parçalı grafik, tam grafik ${ displaystyle K_ {4}}$veya a üçgen kitap ${ displaystyle K_ {1,1, n}}$.^[2] Bu üç tür çift bağlantılı bileşen, kendi başına mükemmel grafikler olduğundan, her çizgi mükemmel grafiğin kendisi mükemmeldir.^[1] Benzer mantıkla, her çizgi mükemmel grafik bir eşlik grafiği,^[3] a Meyniel grafiği,^[4] ve bir mükemmel sıralanabilir grafik.

Kusursuz çizgi grafikler, çift taraflı grafikleri genelleştirir ve onlarla, maksimum eşleşme ve minimum köşe örtüsü aynı boyutta ve kromatik indeks eşittir maksimum derece.^[5]

Ayrıca bakınız

• Boğulmuş grafik, her birinin çevresel döngü bir üçgen

Referanslar