Universality in Graph Properties with Degree Restrictions

• Autorzy: Izak Broere , Johannes Heidema , Peter Mihók
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

countable graph; universal graph; induced-hereditary; k-degenerate graph; graph with colouring number at most k + 1; graph property with assignment

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2013
• Tom: 33
• Numer: 3
• Strony: 477-492

Daty

wydano

2013-07-01

online

2013-07-30

Twórcy

autor

Izak Broere

• Department of Mathematics and Applied Mathematics University of Pretoria Pretoria, South Africa

autor

Johannes Heidema

• Department of Mathematical Sciences University of South Africa Pretoria, South Africa

autor

Peter Mihók

• Department of Applied Mathematics Technical University of Košice Košice, Slovakia

Bibliografia

• [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]
• [2] I. Broere and J. Heidema, Some universal directed labelled graphs, Util. Math. 84 (2011) 311-324.
• [3] I. Broere and J. Heidema, Universal H-colourable graphs, Graphs Combin., accepted for publication. doi:10.1007/s00373-012-1216-5[Crossref]
• [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]
• [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]
• [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]
• [7] R. Diestel, Graph theory (Fourth Edition, Graduate Texts in Mathematics, 173; Springer, Heidelberg, 2010).
• [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]
• [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.
• [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]
• [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]
• [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]
• [17] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340.

Identyfikatory

DOI

10.7151/dmgt.1696