Universality in Graph Properties with Degree Restrictions

Izak Broere ; Johannes Heidema ; Peter Mihók

Discussiones Mathematicae Graph Theory, Tome 33 (2013), p. 477-492 / Harvested from The Polish Digital Mathematics Library

Résumé

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.

Détail

Publié le : 2013-01-01

Zbl 1274.05334

EUDML-ID : urn:eudml:doc:268159

Bibliographie

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

[2] I. Broere and J. Heidema, Some universal directed labelled graphs, Util. Math. 84 (2011) 311-324. | Zbl 1228.05250

[3] I. Broere and J. Heidema, Universal H-colourable graphs, Graphs Combin., accepted for publication. doi:10.1007/s00373-012-1216-5[Crossref] | Zbl 1272.05136

[4] I. Broere, J. Heidema and P. Mihók, Constructing universal graphs for inducedhereditary graph properties, Math. Slovaca 63 (2013) 191-200. doi:10.7151/s12175-012-0092-z[Crossref][WoS] | Zbl 1324.05135

[5] G. Cherlin and P. Komjáth, There is no universal countable pentagon-free graph, J. Graph Theory 18 (1994) 337-341. doi:10.1002/jgt.3190180405[Crossref] | Zbl 0805.05044

[6] G. Cherlin and N. Shi, Graphs omitting a finite set of cycles, J. Graph Theory 21 (1996) 351-355. doi:10.1002/(SICI)1097-0118(199603)21:3h351::AID-JGT11i3.0.CO;2-K[Crossref] | Zbl 0845.05060

[7] R. Diestel, Graph theory (Fourth Edition, Graduate Texts in Mathematics, 173; Springer, Heidelberg, 2010). | Zbl 1204.05001

[8] P. Erdös and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Hungar. 17 (1966) 61-99. doi:10.1007/BF02020444[Crossref]

[9] L. Esperet, A. Labourel and P. Ochem, On induced-universal graphs for the class of bounded-degree graphs, Inform. Process. Lett. 108 (2008) 255-260. doi:10.1016/j.ipl.2008.04.020[Crossref][WoS] | Zbl 1189.05162

[10] R. Fraïssé, Sur l’extension aux relations de quelques propriétiés connues des ordres, C. R. Acad. Sci. Paris 237 (1953) 508-510. | Zbl 0053.02904

[11] Z. Füredi and P. Komjáth, On the existence of countable universal graphs, J. Graph Theory 25 (1997) 53-58. doi:10.1002/(SICI)1097-0118(199705)25:1h53::AID-JGT3i3.0.CO;2-H[Crossref]

[12] A. Hajnal and J. Pach, Monochromatic paths in infinite coloured graphs, Finite and infinite sets, Colloquia Mathematica Societatis János Bolyai, Eger, Hungary 37 (1981) 359-369.

[13] C.W. Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971) 69-83. doi:10.2140/pjm.1971.38.69[Crossref]

[14] P. Komjáth and J. Pach, Universal graphs without large bipartite subgraphs, Mathematika 31 (1984) 282-290. doi:10.1112/S002557930001250X[Crossref] | Zbl 0551.05057

[15] D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096. doi:10.4153/CJM-1970-125-1[Crossref] | Zbl 0202.23502

[16] P. Mihók, J. Miškuf and G. Semanišin, On universal graphs for hom-properties, Discuss. Math. Graph Theory 29 (2009) 401-409. doi:10.7151/dmgt.1455[Crossref] | Zbl 1194.05041

[17] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. | Zbl 0139.17303