# Universality in Graph Properties with Degree Restrictions

Izak Broere; Johannes Heidema; Peter Mihók

Discussiones Mathematicae Graph Theory (2013)

- Volume: 33, Issue: 3, page 477-492
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topIzak Broere, Johannes Heidema, and Peter Mihók. "Universality in Graph Properties with Degree Restrictions." Discussiones Mathematicae Graph Theory 33.3 (2013): 477-492. <http://eudml.org/doc/268159>.

@article{IzakBroere2013,

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 [...] 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.},

author = {Izak Broere, Johannes Heidema, Peter Mihók},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {countable graph; universal graph; induced-hereditary; k-degenerate graph; graph with colouring number at most k + 1; graph property with assignment; -degenerate graph; graph with colouring number at most },

language = {eng},

number = {3},

pages = {477-492},

title = {Universality in Graph Properties with Degree Restrictions},

url = {http://eudml.org/doc/268159},

volume = {33},

year = {2013},

}

TY - JOUR

AU - Izak Broere

AU - Johannes Heidema

AU - Peter Mihók

TI - Universality in Graph Properties with Degree Restrictions

JO - Discussiones Mathematicae Graph Theory

PY - 2013

VL - 33

IS - 3

SP - 477

EP - 492

AB - 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.

LA - eng

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

UR - http://eudml.org/doc/268159

ER -

## References

top- [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] Zbl0902.05026
- [2] I. Broere and J. Heidema, Some universal directed labelled graphs, Util. Math. 84 (2011) 311-324. Zbl1228.05250
- [3] I. Broere and J. Heidema, Universal H-colourable graphs, Graphs Combin., accepted for publication. doi:10.1007/s00373-012-1216-5[Crossref] Zbl1272.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] Zbl1324.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] Zbl0805.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] Zbl0845.05060
- [7] R. Diestel, Graph theory (Fourth Edition, Graduate Texts in Mathematics, 173; Springer, Heidelberg, 2010). Zbl1204.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] Zbl1189.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. Zbl0053.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] Zbl0551.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] Zbl0202.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] Zbl1194.05041
- [17] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. Zbl0139.17303