Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
(2016)
Presentation / Conference Contribution
Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016, July). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Presented at 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Rome, Italy
For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with do... Read More about Constraint Satisfaction Problems for Reducts of Homogeneous Graphs.