Geodesic
Universality in Graph Properties with Degree Restrictions
Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 477-492.

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

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 lt; 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 
@article{DMGT_2013_33_3_a0,
     author = {Broere, Izak and Heidema, Johannes and Mih\'ok, Peter},
     title = {Universality in {Graph} {Properties} with {Degree} {Restrictions}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {477--492},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Heidema, Johannes
AU  - Mihók, Peter
TI  - Universality in Graph Properties with Degree Restrictions
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 477
EP  - 492
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/
LA  - en
ID  - DMGT_2013_33_3_a0
ER  - 
%0 Journal Article
%A Broere, Izak
%A Heidema, Johannes
%A Mihók, Peter
%T Universality in Graph Properties with Degree Restrictions
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 477-492
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/
%G en
%F DMGT_2013_33_3_a0
Broere, Izak; Heidema, Johannes; Mihók, Peter. Universality in Graph Properties with Degree Restrictions. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 477-492. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/

[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 inducedhereditary graph properties, Math. Slovaca 63 (2013) 191-200. doi:10.7151/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:3h351::AID-JGT11i3.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:1h53::AID-JGT3i3.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.