Geodesic
The Quest for A Characterization of Hom-Properties of Finite Character
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 479-500.

Voir la notice de l'article provenant de la source Library of Science

A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property → H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property mathcalP is of finite character if, whenever we have that F ∈𝒫 for every finite induced subgraph F of a graph G, then we have that G ∈𝒫 too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for → H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which → H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.
Keywords: (countable) graph, homomorphism (of graphs), property of graphs, hom-property, (finitely-)induced-hereditary property, finitely determined property, (weakly) finite character, axiomatizable property, compactness theorems, core, connectedness, chromatic number, clique number, independence number, dominating set 
@article{DMGT_2016_36_2_a17,
     author = {Broere, Izak and Matsoha, Moroli D.V. and Heidema, Johannes},
     title = {The {Quest} for {A} {Characterization} of {Hom-Properties} of {Finite} {Character}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {479--500},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a17/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Matsoha, Moroli D.V.
AU  - Heidema, Johannes
TI  - The Quest for A Characterization of Hom-Properties of Finite Character
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 479
EP  - 500
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a17/
LA  - en
ID  - DMGT_2016_36_2_a17
ER  - 
%0 Journal Article
%A Broere, Izak
%A Matsoha, Moroli D.V.
%A Heidema, Johannes
%T The Quest for A Characterization of Hom-Properties of Finite Character
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 479-500
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a17/
%G en
%F DMGT_2016_36_2_a17
Broere, Izak; Matsoha, Moroli D.V.; Heidema, Johannes. The Quest for A Characterization of Hom-Properties of Finite Character. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 479-500. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a17/

[1] B.L. Bauslaugh, Core-like properties of infinite graphs and structures, Discrete Math. 138 (1995) 101-111. doi:10.1016/0012-365X(94)00191-K

[2] B.L. Bauslaugh, Cores and compactness of infinite directed graphs, J. Combin. Theory Ser. B 68 (1996) 255-276.

[3] B.L. Bauslaugh, List-Compactness of directed graphs, Graphs Combin. 17 (2001) 17-38. doi:10.1007/s003730170052

[4] M. Borowiecki, I. Broere, M. Frick, G. Semanišin and P. Mihók, A survey of hered- itary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037

[5] J. Bucko and P. Mihók, On infinite uniquely partitionable graphs and graph proper- ties of finite character, Discuss. Math. Graph Theory 29 (2009) 241-251. doi:10.7151/dmgt.1444

[6] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, Fifth Edition (CRC Press, Boca Raton, 2011).

[7] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems, Sci. Math. Jpn. 56 (2002) 171-180.

[8] B.A. Davey and H.A. Priestly, Introduction to Lattices and Order, Second Edition (Cambridge University Press, New York, 2008).

[9] N.G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951) 371-373. doi:10.1016/S1385-7258(51)50053-7

[10] R. Diestel, Graph Theory, Fourth Edition (Graduate Texts in Mathematics 173, Springer, Heidelberg, 2010). doi:10.1007/978-3-642-14279-6

[11] J.H. Hattingh, Relatiewe semantiese afleibaarheid [Relative semantical entailment] (Master’s dissertation (in Afrikaans), Rand Afrikaans University, Johannesburg, 1985).

[12] T.W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of Domination in Graphs (Marcel Dekker Inc., New York, 1998).

[13] P. Hell and J. Nešetřil, Graphs and Homomorphisms (Oxford University Press, Oxford, 2004).

[14] W. Hodges, First-order Model Theory (The Stanford Encyclopedia of Philosophy (Summer 2009 Edition), E.N. Zalta (Ed.), 2009). http://plato.stanford.edu/archives/sum2009/entries/modeltheory-fol

[15] R. Kellerman, private communication.

[16] A. Robinson, Introduction to Model Theory and to the Metamathematics of Algebra (North-Holland, Amsterdam, 1963).

[17] A. Salomaa, On color-families of graphs, Ann. Acad. Sci. Fenn. Math. 6 (1981) 135-148. doi:10.5186/aasfm.1981.0619

[18] E. Welzl, Color-families are dense, Theoret. Comput. Sci. 17 (1982) 29-41. doi:10.1016/0304-3975(82)90129-3