<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>744</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-07-14</completedDate>
    <publishedDate>2003-07-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Critical and Anticritical Edges with respect to Perfectness</title>
    <abstract language="eng">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 &amp; 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 &amp; Wagler 2002}] showing that perfectness is an elusive graph property.</abstract>
    <identifier type="serial">03-22</identifier>
    <identifier type="opus3-id">745</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7446</identifier>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Perfect graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>critical edges</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect edge orders</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>critically perfect graphs</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C17">Perfect graphs</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/744/ZR-03-22.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/744/ZR-03-22.pdf</file>
  </doc>
  <doc>
    <id>597</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-09-08</completedDate>
    <publishedDate>2000-09-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Classes of Critically and Anticritically Perfect Graphs</title>
    <abstract language="eng">We focus on two new types of extremal graphs with respect to perfectness: critically and anticritically perfect graphs that lose their perfectness by simply deleting and adding an arbitrary edge, respectively. We present examples and study properties in order to compare critically and anticritically perfect graphs with minimally imperfect graphs, another type of extremal graphs with respect to perfectness. We discuss two attempts to characterize the classes of all critically and anticritically perfect graphs and give a brief overview on classes of perfect graphs which contain critically or anticritically perfect graphs.</abstract>
    <identifier type="serial">00-29</identifier>
    <identifier type="opus3-id">598</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-5975</identifier>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-29</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>critically perfect graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>anticritically perfect graphs</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05Cxx">Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15)</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/597/ZR-00-29.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/597/ZR-00-29.pdf</file>
  </doc>
</export-example>
