Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 1 of 17
Back to Result List

Critical and Anticritical Edges in Perfect Graphs

Please always quote using this URN: urn:nbn:de:0297-zib-6174
  • We call an edge $e$ of a perfect graph $G$ critical if $G-e$ is imperfect and say further that $e$ is anticritical with respect to the complementary graph $\overline G$. We ask in which perfect graphs critical and anticritical edges occur and how to find critical and anticritical edges in perfect graphs. Finally, we study whether we can order the edges of certain perfect graphs such that deleting all the edges yields a sequence of perfect graphs ending up with a stable set.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Annegret Wagler
Document Type:ZIB-Report
Tag:anticritical edges; critical edges; perfect graphs
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15)
Date of first Publication:2000/12/15
Series (Serial Number):ZIB-Report (00-49)
ZIB-Reportnumber:00-49
Published in:Appeared in: Proc. of the 27th Workshop on Graph-Theoretic Concepts in Computer Science. Springer 2001, Lecture Notes in Computer Science 2204, pp. 317-327
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.