Perfectness is an Elusive Graph Property
Please always quote using this URN: urn:nbn:de:0297-zib-6787
- 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.
Download full text files
Additional Services
| Author: | Stefan Hougardy, Annegret Wagler |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | elusive graph property; perfect graph |
| 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 |
| 68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R05 Combinatorics | |
| Date of first Publication: | 2002/02/28 |
| Series (Serial Number): | ZIB-Report (02-11) |
| ZIB-Reportnumber: | 02-11 |
| Published in: | Appeared in: SIAM Journal on Computing 34 (2004) 109-117 |
