DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(3) (2013) 477-492
DOI: https://doi.org/10.7151/dmgt.1696

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.

Received 28 February 2012
Revised 29 October 2012
Accepted 29 October 2012

Close