SOME RESULTS ON ELUSIVE GRAPH PROPERTIES

Authors
TRIESCH E
Citation
E. Triesch, SOME RESULTS ON ELUSIVE GRAPH PROPERTIES, SIAM journal on computing, 23(2), 1994, pp. 247-254
Citations number
17
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
23
Issue
2
Year of publication
1994
Pages
247 - 254
Database
ISI
SICI code
0097-5397(1994)23:2<247:SROEGP>2.0.ZU;2-6
Abstract
This article proves several graph properties to be elusive. Two of the main results are 1. If P is a decreasing graph property containing no graph of girth smaller than 5, then P is elusive. 2. The property of having matching number at most k, k < left perpendicular\V\/2right per pendicular, is elusive. The proofs are all based on a topological meth od developed by Kahn, Saks, and Sturtevant.