<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>883</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-11-30</completedDate>
    <publishedDate>2005-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Comparing Imperfection Ratio and Imperfection Index for Graph Classes</title>
    <abstract language="eng">Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of $STAB( G)$, the disjunctive index of $QSTAB(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB(G)$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of $STAB(G)$ and $QSTAB(G)$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of $Q STAB(G)$ as the imperfection index of $G$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.</abstract>
    <identifier type="serial">05-50</identifier>
    <identifier type="opus3-id">883</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8836</identifier>
    <enrichment key="SourceTitle">Appeared in: RAIRO-Oper. Res. 42 (2008) 485-500</enrichment>
    <author>Arie M.C.A. Koster</author>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-50</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect graphs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>imperfection ratio</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>imperfection index</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C17">Perfect graphs</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="StableSets">StableSets</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/883/ZR-05-50.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/883/ZR-05-50.ps</file>
  </doc>
  <doc>
    <id>297</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-06-30</completedDate>
    <publishedDate>1997-06-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Minimally non-preperfect graphs of small maximum degree</title>
    <abstract language="eng">A graph $G$ is called preperfect if each induced subgraph $G' \subseteq G$ of order at least 2 has two vertices $x,y$ such that either all maximum cliques of $G'$ containing $x$ contain $y$, or all maximum indepentent sets of $G'$ containing $y$ contain $x$, too. Giving a partial answer to a problem of Hammer and Maffray [Combinatorica 13 (1993), 199-208], we describe new classes of minimally non-preperfect graphs, and prove the following characterizations: \begin{itemize} \item[(i)] A graph of maximum degree 4 is minimally non-preperfect if and only if it is an odd cycle of length at least 5, or the complement of a cycle of length 7, or the line graph of a 3-regular 3-connected bipartite graph. \item[(ii)] If a graph $G$ is not an odd cycle and has no isolated vertices, then its line graph is minimally non-preperfect if and only if $G$ is bipartite, 3-edge-connected, regular of degree $d$ for some $d \ge 3$, and contains no 3-edge-connected $d'$-regular subgraph for any $3 \le d' \le d$. \end{itemize}</abstract>
    <identifier type="serial">SC-97-28</identifier>
    <identifier type="opus3-id">298</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2971</identifier>
    <enrichment key="SourceTitle">Appeared in: Graphs and Combinatorics 17 (2001) 759-773</enrichment>
    <author>Zsolt Tuza</author>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-28</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/297/SC-97-28.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/297/SC-97-28.pdf</file>
  </doc>
  <doc>
    <id>260</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1996-12-04</completedDate>
    <publishedDate>1996-12-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On Critically Perfect Graphs</title>
    <abstract language="eng">A perfect graph is critical if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We investigate the relationship of critically perfect graphs to well-known classes of perfect graphs and study operations preserving critical perfectness.</abstract>
    <identifier type="serial">SC-96-50</identifier>
    <identifier type="opus3-id">261</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-2609</identifier>
    <enrichment key="SourceTitle">Appeared in: J. Graph Theory 32 (1999) pp. 394-404</enrichment>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-96-50</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/260/SC-96-50.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/260/SC-96-50.pdf</file>
  </doc>
</export-example>
