# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

## Universality in graph properties with degree restrictions

 Izak Broere Department of Mathematics and Applied Mathematics University of Pretoria Pretoria, South Africa Johannes Heidema Department of Mathematical Sciences University of South Africa Pretoria, South Africa Peter Mihók Department of Applied Mathematics Technical University of Košice Košice, Slovakia

## Abstract

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 ℑc of all countable graphs (since every graph in ℑc is isomorphic to an induced subgraph of R).

A brief overview of known universality results for some induced-hereditary subsets of ℑc 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.

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

2010 Mathematics Subject Classification: 05C63.

## References

 [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 . [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. [4] I. Broere, J. Heidema and P. Mihók, Constructing universal graphs for induced-hereditary graph properties, Math. Slovaca 63 (2013) 191--200, doi: 10.2478/s12175-012-0092-z. [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. [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:3<351::AID-JGT11>3.0.CO;2-K. [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 . [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. [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:1<53::AID-JGT3>3.0.CO;2-H. [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. [14] P. Komjáth and J. Pach, Universal graphs without large bipartite subgraphs, Mathematika 31 (1984) 282--290, doi: 10.1112/S002557930001250X. [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. [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. [17] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331--340.