Élperfekt gráf

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.^[1]

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).^[2] Mivel mindháromfajta kétszeresen összefüggő komponenens maga is perfekt gráf, ezért az élperfekt gráfok mindig perfekt gráfok is.^[1] Hasonló okoskodás alapján minden élperfekt gráf egyben paritásgráf,^[3] Meyniel-gráf^[4] é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.^[5]

Kapcsolódó szócikkek

Lekötött gráf

Fordítás

Ez a szócikk részben vagy egészben a Line perfect graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ ^a ^b Trotter, L. E., Jr. (1977), "Line perfect graphs", Mathematical Programming 12 (2): 255–259, DOI 10.1007/BF01593791
↑ Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory, Series B 55 (1): 1–8, DOI 10.1016/0095-8956(92)90028-V.
↑ Grötschel, Martin; Lovász, László & Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, vol. 2 (2nd ed.), Algorithms and Combinatorics, Springer-Verlag, Berlin, p. 281, ISBN 3-540-56740-2, doi:10.1007/978-3-642-78240-4, <https://books.google.com/books?id=hWvmCAAAQBAJ&pg=PA281>.
↑ Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, vol. 2204, Lecture Notes in Computer Science, Berlin: Springer, pp. 317–327, DOI 10.1007/3-540-45477-2_29.
↑ de Werra, D. (1978), "On line-perfect graphs", Mathematical Programming 15 (2): 236–238, DOI 10.1007/BF01609025.

Matematikaportál • összefoglaló, színes tartalomajánló lap

[trotter-1] Trotter, L. E., Jr. (1977), "Line perfect graphs", Mathematical Programming 12 (2): 255–259, DOI 10.1007/BF01593791

[maffray-2] Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory, Series B 55 (1): 1–8, DOI 10.1016/0095-8956(92)90028-V.

[gls-3] Grötschel, Martin; Lovász, László & Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, vol. 2 (2nd ed.), Algorithms and Combinatorics, Springer-Verlag, Berlin, p. 281, ISBN 3-540-56740-2, doi:10.1007/978-3-642-78240-4, <https://books.google.com/books?id=hWvmCAAAQBAJ&pg=PA281>.

[wagler-4] Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, vol. 2204, Lecture Notes in Computer Science, Berlin: Springer, pp. 317–327, DOI 10.1007/3-540-45477-2_29.

[dewerra-5] Werra, D. (1978), "On line-perfect graphs", Mathematical Programming 15 (2): 236–238, DOI 10.1007/BF01609025.

[1]

[2]

[3]

[4]

[5]