Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
(2016)
Conference Proceeding
Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016. https://doi.org/10.4230/lipics.icalp.2016.119
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.