Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T17:48:17.706Z Has data issue: false hasContentIssue false
  • English
  • Français

RESIDUAL PROPERTIES OF SIMPLE GRAPHS

Part of: Graph theory Low-dimensional topology

Published online by Cambridge University Press:  18 August 2010

BELINDA TROTTA
BELINDA TROTTA*
Affiliation:
Department of Mathematics and Statistics, La Trobe University, Bundoora, Victoria 3086, Australia (email: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

random graphgraph colouringBoolean topological graphuniversal Horn classaxiomatization

MSC classification

Secondary: 05C80: Random graphs 05C15: Coloring of graphs and hypergraphs 57M15: Relations with graph theory
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 82 , Issue 3 , December 2010 , pp. 488 - 504
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2010

References

[1]Burris, S. and Sankappanavar, H. P., ‘A course in universal algebra’, online athttp://www.math.uwaterloo.ca/∼snburris/htdocs/ualg.html, originally published in 1981.CrossRefGoogle Scholar
[2]Caicedo, X., ‘Finitely axiomatisable quasivarieties of graphs’, Algebra Universalis 34 (1995), 314–321.CrossRefGoogle Scholar
[3]Clark, D. M., Davey, B. A., Freese, R. S. and Jackson, M., ‘Standard topological algebras: syntactic and principal congruences and profiniteness’, Algebra Universalis 52 (2004), 343–376.CrossRefGoogle Scholar
[4]Clark, D. M., Davey, B. A., Haviar, M., Pitkethly, J. G. and Talukder, M. R., ‘Standard topological quasi-varieties’, Houston J. Math. 4 (2003), 859–887.Google Scholar
[5]Clark, D. M., Davey, B. A., Jackson, M. G. and Pitkethly, J. G., ‘The axiomatizability of topological prevarieties’, Adv. Math. 218 (2008), 1604–1653.CrossRefGoogle Scholar
[6]Davey, B. A., ‘Natural dualities for structures’, Acta Univ. M. Belii Ser. Math. 13 (2006), 3–28.Google Scholar
[7]Davey, B. A. and Talukder, M. R., ‘Dual categories for endodualisable Heyting algebras: optimization and axiomatization’, Algebra Universalis 53 (2005), 331–355.Google Scholar
[8]Edwards, C., ‘Standardness of small topological structures’, MSc Thesis, La Trobe University, 2005.Google Scholar
[9]Feder, T. and Vardi, M. Y., ‘The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory’, SIAM J. Comput. 28 (1998), 57–104.CrossRefGoogle Scholar
[10]Hell, P. and Nešetřil, J., ‘The core of a graph’, Discrete Math. 109 (1992), 117–126.CrossRefGoogle Scholar
[11]Hodkinson, I. and Venema, Y., ‘Canonical varieties with no canonical axiomatisation’, Trans. Amer. Math. Soc. 357 (2005), 4579–4605.CrossRefGoogle Scholar
[12]Jackson, M., ‘Residual bounds for compact totally disconnected algebras’, Houston J. Math. 34 (2008), 33–67.Google Scholar
[13]Nešetřil, J. and Pultr, A., ‘On classes of relations and graphs determined by subobjects and factorobjects’, Discrete Math. 22 (1978), 287–300.CrossRefGoogle Scholar
[14]Stralka, A., ‘A partially ordered space which is not a Priestley space’, Semigroup Forum 20 (1980), 293–297.CrossRefGoogle Scholar
[15]Trotta, B., ‘Residual properties of pre-bipartite digraphs’, Algebra Universalis, to appear.Google Scholar
[16]Trotta, B., ‘Residual properties of reflexive anti-symmetric digraphs’, Houston J. Math., to appear.Google Scholar