<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>678</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-02-28</completedDate>
    <publishedDate>2002-02-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Perfectness is an Elusive Graph Property</title>
    <abstract language="eng">A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.</abstract>
    <identifier type="serial">02-11</identifier>
    <identifier type="opus3-id">679</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6787</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM Journal on Computing 34 (2004) 109-117</enrichment>
    <author>Stefan Hougardy</author>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-11</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect graph</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elusive graph property</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C17">Perfect graphs</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/678/ZR-02-11.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/678/ZR-02-11.pdf</file>
  </doc>
</export-example>
