RESIDUAL PROPERTIES OF SIMPLE GRAPHS

Abstract

Abstract Clark et al. [‘The axiomatizability of topological prevarieties’, Adv. Math. 218 (2008), 1604–1653] have shown that, for k ≥2, there exists a Boolean topological graph that is k -colourable but not topologically k -colourable; that is, for every ϵ>0, it cannot be coloured by a paintbrush of width ϵ. We generalize this result to show that, for k ≥2, there is a Boolean topological graph that is 2-colourable but not topologically k -colourable. This graph is an inverse limit of finite graphs which are shown to exist by an Erdős-style probabilistic argument of Hell and Nešetřil [‘The core of a graph’, Discrete Math. 109 (1992), 117–126]. We use the fact that there exists a Boolean topological graph that is 2-colourable but not k -colourable, and some other results (some new and some previously known), to answer the question of which finitely generated topological residual classes of graphs are axiomatizable by universal Horn sentences. A more general version of this question was raised in the above-mentioned paper by Clark et al ., and has been investigated by various authors for other structures.