Okrajově dokonalý graf

Hraně dokonalý graf je graf, jehož spojnicový graf je dokonalý . Ekvivalentně se jedná o grafy, kde každý jednoduchý cyklus liché délky je trojúhelník [1] .

Graf je hranově dokonalý právě tehdy, když některá z jeho dvojitě propojených složek je bipartitní graf , úplný graf nebo kniha trojúhelníků [2] . Protože tyto tři typy dvojitě spojených komponent jsou samy o sobě dokonalými grafy, je každý graf s hranovou dokonalostí sám o sobě dokonalý [1] . Z podobných důvodů je každý graf s hranou dokonalým grafem paritní [3] , Meinelův graf [4] a dobře uspořádaný graf .

Edge-perfect grafy zobecňují bipartitní grafy a sdílejí s nimi vlastnosti, že největší shoda a nejmenší vertexové pokrytí mají stejnou velikost a chromatický index je roven maximálnímu stupni [5] .

Viz také

Poznámky

  1. ↑ 12 Trotter LE, Jr. Dokonalé čárové grafy // Matematické programování . - 1977. - T. 12 , no. 2 . — S. 255–259 . - doi : 10.1007/BF01593791 .
  2. ↑ Frederic Maffray. Jádra v dokonalých spojnicových grafech // Journal of Combinatorial Theory . - 1992. - T. 55 , no. 1 . — S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V . .
  3. ↑ Martin Grötschel, László Lovász, Alexander Schrijver. Geometrické algoritmy a kombinatorická optimalizace . — 2. - Springer-Verlag, Berlin, 1993. - V. 2. - S. 281. - (Algoritmy a kombinatorika). — ISBN 3-540-56740-2 . - doi : 10.1007/978-3-642-78240-4 . .
  4. ↑ Annegret Wagler. Kritické a antikritické hrany v dokonalých grafech // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14-16, 2001, Proceedings. - Springer, 2001. - T. 2204. - S. 317-327. — (Poznámky z informatiky). - doi : 10.1007/3-540-45477-2_29 . .
  5. ↑ On line-perfect grafy // Matematické programování . - 1978. - T. 15 . - S. 236-238. - doi : 10.1007/BF01609025 . .