Perfektní spojnicový graf - Line perfect graph

Perfektní spojnicový graf. Okraje v každé vzájemně propojené složce jsou zbarveny černě, pokud je složka bipartitní, modře, pokud je složkou čtyřstěn, a červeně, pokud je složkou kniha trojúhelníků.

v teorie grafů, a řádkový dokonalý graf je graf, jehož hranový graf je perfektní graf. Ekvivalentně se jedná o grafy, ve kterých je každá lichá délka jednoduchý cyklus je trojúhelník.^[1]

Graf je perfektní čára právě tehdy, když je každý vzájemně propojené komponenty je bipartitní graf, kompletní graf ${ displaystyle K_ {4}}$ nebo trojúhelníková kniha ${ displaystyle K_ {1,1, n}}$ .^[2] Protože tyto tři typy vzájemně propojených komponent jsou samy o sobě dokonalými grafy, je každý perfektní řádkový graf dokonalý.^[1] Podle podobného uvažování je každý řádkový dokonalý graf a paritní graf,^[3] A Meynielův graf,^[4] a a dokonale uspořádatelný graf.

Perfektní spojnicové grafy zobecňují bipartitní grafy a sdílejí s nimi vlastnosti, které maximální shoda a minimální vrcholový kryt mají stejnou velikost a že chromatický index rovná se maximální stupeň.^[5]

Viz také

Zúžený graf, graf, ve kterém každý periferní cyklus je trojúhelník

Reference

^ ^A ^b Trotter, L. E., Jr. (1977), „Line perfect graphs“, Matematické programování, 12 (2): 255–259, doi:10.1007 / BF01593791, PAN 0457293
^ Maffray, Frédéric (1992), „Jádra v dokonalých liniových grafech“, Journal of Combinatorial Theory, Řada B, 55 (1): 1–8, doi:10.1016 / 0095-8956 (92) 90028-V, PAN 1159851.
^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometrické algoritmy a kombinatorická optimalizace Algoritmy a kombinatorika, 2 (2. vyd.), Springer-Verlag, Berlín, s. 281, doi:10.1007/978-3-642-78240-4, ISBN 3-540-56740-2, PAN 1261419.
^ Wagler, Annegret (2001), „Kritické a antikritické hrany v dokonalých grafech“, Graficko-teoretické koncepty v informatice: 27. mezinárodní workshop, WG 2001, Boltenhagen, Německo, 14. – 16. Června 2001, sborník, Přednášky v informatice, 2204, Berlín: Springer, s. 317–327, doi:10.1007/3-540-45477-2_29, PAN 1905643.
^ de Werra, D. (1978), „On line-perfect graphs“, Matematické programování, 15 (2): 236–238, doi:10.1007 / BF01609025, PAN 0509968.

[trotter-1] A ^b Trotter, L. E., Jr. (1977), „Line perfect graphs“, Matematické programování, 12 (2): 255–259, doi:10.1007 / BF01593791, PAN 0457293

[maffray-2] Maffray, Frédéric (1992), „Jádra v dokonalých liniových grafech“, Journal of Combinatorial Theory, Řada B, 55 (1): 1–8, doi:10.1016 / 0095-8956 (92) 90028-V, PAN 1159851.

[gls-3] Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometrické algoritmy a kombinatorická optimalizace Algoritmy a kombinatorika, 2 (2. vyd.), Springer-Verlag, Berlín, s. 281, doi:10.1007/978-3-642-78240-4, ISBN 3-540-56740-2, PAN 1261419.

[wagler-4] Wagler, Annegret (2001), „Kritické a antikritické hrany v dokonalých grafech“, Graficko-teoretické koncepty v informatice: 27. mezinárodní workshop, WG 2001, Boltenhagen, Německo, 14. – 16. Června 2001, sborník, Přednášky v informatice, 2204, Berlín: Springer, s. 317–327, doi:10.1007/3-540-45477-2_29, PAN 1905643.

[dewerra-5] Werra, D. (1978), „On line-perfect graphs“, Matematické programování, 15 (2): 236–238, doi:10.1007 / BF01609025, PAN 0509968.

[1]

[2]

[3]

[4]

[5]