Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Critical and Anticritical Edges with respect to Perfectness

Please always quote using this URN: urn:nbn:de:0297-zib-7446
  • We call an edge $e$ of a perfect graph $G$ critical if $G-e$ is imperfect and call $e$ anticritical if $G+e$ is imperfect. The present paper surveys several questions in this context. We ask in which perfect graphs critical and anticritical edges occur and how to detect such edges. The main result by [{\sl Wagler, PhD thesis 2000}] shows that a graph does not admit any critical edge if and only if it is Meyniel. The goal is to order the edges resp.~non-edges of certain perfect graphs s.t. deleting resp.~adding all edges in this order yields a sequence of perfect graphs only. Results of [{\sl Hayward 1985}] and [{\sl Spinrad & Sritharan 1995}] show the existence of such edge orders for weakly triangulated graphs; the line-perfect graphs are precisely these graphs where all edge orders are perfect [{\sl Wagler 2001}]. Such edge orders cannot exist for every subclass of perfect graphs that contains critically resp.~anticritically perfect graphs where deleting resp.~adding an arbitrary edge yields an imperfect graph. We present several examples and properties of such graphs, discuss constructions and characterizations from [{\sl Wagler 1999, Wagler PhD thesis 2000}]. An application of the concept of critically and anticritically perfect graphs is a result due to [{\sl Hougardy & Wagler 2002}] showing that perfectness is an elusive graph property.

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:Perfect graphs; critical edges; critically perfect graphs; perfect edge orders
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) / 05C17 Perfect graphs
Date of first Publication:2003/07/14
Series (Serial Number):ZIB-Report (03-22)
ZIB-Reportnumber:03-22
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.