Discussiones Mathematicae Graph Theory 33(3) (2013)
477-492

doi: 10.7151/dmgt.1696

Izak Broere
Department of Mathematics and Applied Mathematics | Johannes Heidema
Department of Mathematical Sciences | Peter Mihók
Department of Applied Mathematics |

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.

[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 , Graphs Combin., accepted for publication, doi: 10.1007/s00373-012-1216-5.H-colourable graphs |

[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, , Canad. J. Math. k-degenerate graphs 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. |

Received 28 February 2012

Revised 29 October 2012

Accepted 29 October 2012