Edge-tökéletes grafikon

Az él-tökéletes gráf olyan gráf, amelynek vonalgráfja tökéletes . Ezek olyan gráfok, ahol minden páratlan hosszúságú egyszerű ciklus egy háromszög [1] .

Egy gráf éltökéletes akkor és csak akkor, ha bármely kétszeresen összefüggő komponense kétrészes gráf , teljes gráf vagy háromszögek könyve [2] . Mivel ez a három típusú kétszeresen összefüggő komponens önmagában is tökéletes gráf, minden él-tökéletes gráf maga is tökéletes [1] . Hasonló okokból bármely élperfekt gráf paritásgráf [3] , Meinel gráf [4] és jól rendezett gráf .

Az él-tökéletes gráfok általánosítják a kétrészes gráfokat, és megosztják velük azokat a tulajdonságokat, hogy a legnagyobb illeszkedés és a legkisebb csúcsfedés azonos méretű, a kromatikus index pedig megegyezik a maximális mértékkel [5] .

Lásd még

Jegyzetek

  1. ↑ 12 Trotter LE, Jr. Tökéletes vonalgráfok // Matematikai programozás . - 1977. - T. 12 , sz. 2 . – S. 255–259 . - doi : 10.1007/BF01593791 .
  2. ↑ Frederic Maffray. Kernelek tökéletes vonalgráfokban // Journal of Combinatorial Theory . - 1992. - T. 55 , sz. 1 . – S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V . .
  3. ↑ Martin Grötschel, Lovász László, Alexander Schrijver. Geometriai algoritmusok és kombinatorikus optimalizálás . — 2. - Springer-Verlag, Berlin, 1993. - V. 2. - S. 281. - (Algoritmusok és kombinatorika). — ISBN 3-540-56740-2 . - doi : 10.1007/978-3-642-78240-4 . .
  4. ↑ Annegret Wagler. Kritikus és antikritikus élek tökéletes gráfokban // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Németország, 2001. június 14–16., Proceedings. - Springer, 2001. - T. 2204. - S. 317-327. — (Számítástechnikai előadásjegyzetek). - doi : 10.1007/3-540-45477-2_29 . .
  5. ↑ On line-perfect grafikonok // Matematikai programozás . - 1978. - T. 15 . - P. 236-238. - doi : 10.1007/BF01609025 . .