Transitive graphs in counterexamples to Karp's conjecture

Autor:	Engstr��m, Alexander
Jazyk:	angličtina
Rok vydání:	2005
Předmět:	Computer Science::Discrete Mathematics FOS: Mathematics Algebraic Topology (math.AT) Mathematics - Combinatorics Combinatorics (math.CO) Mathematics - Algebraic Topology Computer Science::Computational Complexity Computer Science::Data Structures and Algorithms 05C15 57M15
Popis:	Karp conjectured that all nontrivial monotone graph properties are evasive. This was proved for n a prime power, and n=6, where n is the number of graph vertices, by Kahn, Saks, and Sturtevant. We give a complete description of which transitive graphs are contained in a possible counterexample when n=10. 18 pages
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5ef836108e8f98f39d9054eb9d3c1f72 http://arxiv.org/abs/math/0512421 Zobrazit plný text záznamu