Grafic perfect

Un grafic cu muchie perfectă este un grafic al cărui grafic cu linii este perfect . În mod echivalent, acestea sunt grafice în care fiecare ciclu simplu de lungime impară este un triunghi [1] .

Un graf este perfect la margini dacă și numai dacă oricare dintre componentele sale dublu conectate este un graf bipartit , un graf complet sau o carte de triunghiuri [2] . Deoarece aceste trei tipuri de componente dublu conectate sunt ele însele grafice perfecte, orice graf perfect cu muchia este el însuși perfect [1] . Din motive similare, orice graf cu muchii perfecte este un graf de paritate [3] , un graf Meinel [4] , și un grafic bine ordonat .

Graficele cu muchii perfecte generalizează graficele bipartite și împărtășesc cu ele proprietățile că cea mai mare potrivire și cea mai mică acoperire a vârfurilor au aceeași dimensiune, iar indicele cromatic este egal cu gradul maxim [5] .

Vezi și

Note

  1. ↑ 12 Trotter LE, Jr. Grafice cu linii perfecte // Programare matematică . - 1977. - T. 12 , nr. 2 . — S. 255–259 . - doi : 10.1007/BF01593791 .
  2. ↑ Frederic Maffray. Kernels in perfect line-graphs // Journal of Combinatorial Theory . - 1992. - T. 55 , nr. 1 . — S. 1–8 . - doi : 10.1016/0095-8956(92)90028-V . .
  3. ↑ Martin Grötschel, László Lovász, Alexander Schrijver. Algoritmi geometrici si optimizare combinatorie . — al 2-lea. - Springer-Verlag, Berlin, 1993. - V. 2. - S. 281. - (Algoritmi și combinatorică). — ISBN 3-540-56740-2 . - doi : 10.1007/978-3-642-78240-4 . .
  4. ↑ Annegret Wagler. Muchii critice și anticritice în grafice perfecte // Concepte teoretice grafice în informatică: 27th International Workshop, WG 2001, Boltenhagen, Germania, 14–16 iunie 2001, Proceedings. - Springer, 2001. - T. 2204. - S. 317-327. — (Note de curs în Informatică). - doi : 10.1007/3-540-45477-2_29 . .
  5. ↑ Pe grafice cu linie perfectă // Programare matematică . - 1978. - T. 15 . - P. 236-238. - doi : 10.1007/BF01609025 . .