Constructing universal graphs for induced-hereditary graph properties

Show simple item record Broere, Izak Heidema, Johannes Mihok, Peter 2013-04-16T11:11:26Z 2013-04-16T11:11:26Z 2013-04
dc.description.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 Ic of all countable graphs (since every graph in Ic is isomorphic to an induced subgraph of R). In this paper we construct graphs which are universal in or for P for di erent inducedhereditary properties P of countable graphs. Constructions of universal graphs for the graph properties containing all graphs with colouring-number at most k+1 and k-degenerate graphs are obtained by restricting the edges of R. Results on the properties of these graphs are given and relationships between them are explored. This is followed by a general recursive construction which proves the existence of a countable universal graph for any induced-hereditary property of countable general graphs. A general construction of universal graphs for products of properties of graphs is also presented. The paper is concluded by a comparison between the two types of constructions of universal graphs. en_US
dc.description.librarian hb2013 en_US
dc.description.sponsorship Research of the third author was supported by VEGA Grant No. 2/0194/10.
dc.description.uri en_US
dc.identifier.citation Broere, I, Heidema, J & Mihok, P 2013, 'Constructing universal graphs for induced-hereditary graph properties', Mathematica Slovaca, vol. 63, no. 2, pp. 191-200. en_US
dc.identifier.issn 0139-9918 (print)
dc.identifier.issn 1337-2211 (online)
dc.identifier.other 10.2478/s12175-012-0092-z
dc.language.iso en en_US
dc.publisher Springer en_US
dc.rights © 2013 Mathematical Institute Slovak Academy of Sciences. The original publication is available at en_US
dc.subject Countable graph en_US
dc.subject Universal graph en_US
dc.subject Induced-hereditary graph property en_US
dc.subject Graph with colouring-number k + 1 en_US
dc.subject k- Degenerate graph en_US
dc.subject Product of graph properties en_US
dc.title Constructing universal graphs for induced-hereditary graph properties en_US
dc.type Postprint Article en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record