{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T21:56:29Z","timestamp":1775512589780,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1996,6,1]],"date-time":"1996-06-01T00:00:00Z","timestamp":833587200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1996,6]]},"DOI":"10.1007\/bf01844851","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T20:55:52Z","timestamp":1121288152000},"page":"259-268","source":"Crossref","is-referenced-by-count":7,"title":["On the recognition complexity of some graph properties"],"prefix":"10.1007","volume":"16","author":[{"given":"Eberhard","family":"Triesch","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01844851_CR1","volume-title":"Combinatorial Search","author":"M. Aigner","year":"1988","unstructured":"M. Aigner:Combinatorial Search, Wiley-Teubner, Stuttgart and Chichester, 1988."},{"key":"BF01844851_CR2","volume-title":"A sharpened version of the Aanderaa-Rosenberg conjecture","author":"M. R. Best","year":"1974","unstructured":"M. R. Best, P. Van Emde Boas, H. W. Lenstra Jr.:A sharpened version of the Aanderaa-Rosenberg conjecture, Math. Centrum Tracts, Amsterdam, 1974."},{"key":"BF01844851_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0095-8956(76)90021-6","volume":"21","author":"B. Bollob\u00e1s","year":"1976","unstructured":"B. Bollob\u00e1s: Complete subgraphs are elusive,J. Combin. Theory B 21 (1976), 1\u20137.","journal-title":"J. Combin. Theory"},{"key":"BF01844851_CR4","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s:Extremal Graph Theory, Academic Press, London, 1978."},{"key":"BF01844851_CR5","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0012-365X(91)90008-P","volume":"88","author":"D. Grieser","year":"1991","unstructured":"D. Grieser: Some results on the complexity of sets,Discrete Math. 88 (1991), 179\u2013192.","journal-title":"Discrete Math."},{"issue":"3","key":"BF01844851_CR6","doi-asserted-by":"crossref","first-page":"239","DOI":"10.24033\/asens.961","volume":"65","author":"L. Kaloujnine","year":"1948","unstructured":"L. Kaloujnine: La structure desp-groupes de Sylow des groupes sym\u00e9triques finis,Ann. Sci. Ecole Norm. Sup. (3),65, (1948), 239\u2013276.","journal-title":"Ann. Sci. Ecole Norm. Sup."},{"key":"BF01844851_CR7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF02122695","volume":"10","author":"V. King","year":"1990","unstructured":"V. King: A lower bound for the recognition of digraph properties,Combinatorica 10 (1990), 53\u201359.","journal-title":"Combinatorica"},{"key":"BF01844851_CR8","doi-asserted-by":"crossref","unstructured":"D.J. Kleitman and D.J. Kwiatkowski: Further results on the Aanderaa-Rosenberg conjecture,J. Combin. Theory B (1980), 85\u201395.","DOI":"10.1016\/0095-8956(80)90057-X"},{"key":"BF01844851_CR9","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J. Kahn","year":"1984","unstructured":"J. Kahn, M. Saks andD. Sturtevant: A topological approach to evasiveness,Combinatorica 4 (1984), 297\u2013306.","journal-title":"Combinatorica"},{"key":"BF01844851_CR10","volume-title":"Algebraic Combinatorics via finite group actions","author":"A. Kerber","year":"1991","unstructured":"A. Kerber: Algebraic Combinatorics via finite group actions, BI-Wissenschaftsverlag, Mannheim 1991."},{"key":"BF01844851_CR11","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02565743","volume":"50","author":"R. Oliver","year":"1975","unstructured":"R. Oliver: Fixed point sets of group actions on finite acyclic complexes,Comment. Math. Helv. 50 (1975), 155\u2013177.","journal-title":"Comment. Math. Helv."},{"key":"BF01844851_CR12","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1008299.1008302","volume":"5","author":"A. L. Rosenberg","year":"1973","unstructured":"A. L. Rosenberg:On the time required to recognize properties of graphs: a problem, SIGACT News 5 (1973), 15\u201316.","journal-title":"SIGACT News"},{"key":"BF01844851_CR13","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/0304-3975(76)90053-0","volume":"3","author":"R. L. Rivest","year":"1976\/77","unstructured":"R. L. Rivest andJ. Vuillemin: On recognizing graph properties from adjacency matrices,Theor. Comput. Sci. 3 (1976\/77), 371\u2013384.","journal-title":"Theor. Comput. Sci."},{"key":"BF01844851_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2371271","volume":"63","author":"P. A. Smith","year":"1941","unstructured":"P. A. Smith: Fixed point theorems for periodic transformations,Amer. J. Math. 63 (1941), 1\u20138.","journal-title":"Amer. J. Math."},{"key":"BF01844851_CR15","volume-title":"Algebraic topology","author":"E. H. Spanier","year":"1966","unstructured":"E. H. Spanier:Algebraic topology, McGraw-Hill, New York, 1966."},{"key":"BF01844851_CR16","doi-asserted-by":"crossref","unstructured":"E. Triesch:Elusive properties, in: Combinatorial Theory, Proceddings Schlo\u00df Rauischholzhausen (1982) (D. Jungnickel and K. Vedder, eds.), Springer Lecture Notes in Math., 321\u2013326.","DOI":"10.1007\/BFb0063003"},{"key":"BF01844851_CR17","unstructured":"E. Triesch:\u00dcber die Komplexit\u00e4t von Grapheneigenschaften, Dissertation, Aachen, 1984."},{"key":"BF01844851_CR18","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1137\/S009753979119415X","volume":"23","author":"E. Triesch","year":"1994","unstructured":"E. Triesch: Some results on elusive graph properties,SIAM J. Comput. 23 (1994), 247\u2013254.","journal-title":"SIAM J. Comput."},{"key":"BF01844851_CR19","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/0217031","volume":"17","author":"A. C-C. Yao","year":"1988","unstructured":"A. C-C. Yao: Monotone bipartite graph properties are evasive,SIAM J. Comput. 17 (1988), 517\u2013520.","journal-title":"SIAM J. Comput."}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01844851.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01844851\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01844851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:55:01Z","timestamp":1586328901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01844851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1996,6]]}},"alternative-id":["BF01844851"],"URL":"https:\/\/doi.org\/10.1007\/bf01844851","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}