Élperfekt gráf

Egy élperfekt gráf. Az ábrán az egyes 2-összefüggő komponensek feketék, ha a komponens páros, kékek, ha a komponens tetraéder és pirosak, ha a komponens háromszögű könyv.

A matematika, azon belül a gráfelmélet területén egy élperfekt gráf (line perfect graph) olyan gráf, melynek élgráfja perfekt gráf. Ezzel egyenértékű definíció szerint azok a gráfok élperfektek, melyek minden páratlan hosszúságú egyszerű köre háromszög.Sablon:R

Egy gráf pontosan akkor élperfekt, ha minden kétszeresen összefüggő komponense teljes páros gráf, a $K_4$ teljes gráf vagy egy $K_{1,1,n}$ alakú háromszögű könyv (teljes háromrészes gráf).Sablon:R Mivel mindháromfajta kétszeresen összefüggő komponenens maga is perfekt gráf, ezért az élperfekt gráfok mindig perfekt gráfok is.Sablon:R Hasonló okoskodás alapján minden élperfekt gráf egyben paritásgráf,Sablon:R Meyniel-gráfSablon:R és perfekt rendezhető gráf is.

Az élperfekt gráfok a páros gráfok általánosításai; velük megegyező tulajdonságaik, hogy a maximális elemszámú párosításuk és minimális csúcslefedésük mérete megegyezik, valamint élkromatikus számuk megegyezik maximális fokszámukkal.Sablon:R

Kapcsolódó szócikkek

• Lekötött gráf

Fordítás

• Sablon:Fordítás