Universal H-colourable graphs

dc.contributor.authorBroere, Izak
dc.contributor.authorHeidema, Johannes
dc.contributor.emailizak.broere@up.ac.zaen_US
dc.date.accessioned2012-09-19T07:13:35Z
dc.date.available2012-09-19T07:13:35Z
dc.date.issued2013
dc.description.abstractRado 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 mth 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) and that it is a homogeneous graph (since every isomorphism between two finite induced subgraphs of R extends to an automorphism of R). In this paper we construct a graphU(H) which is H-universal in →Hc, the induced-hereditary hom-property of H-colourable graphs consisting of all (countable) graphs which have a homomorphism into a given (countable) graph H. If H is the (finite) complete graph Kk , then→Hc is the property of k-colourable graphs. The universal graph U(H) is characterised by showing that it is, up to isomorphism, the unique denumerable, H-universal graph in →Hc which is H-homogeneous in →Hc. The graphs H for which U(H) ∼= R are also characterised.With small changes to the definitions, our results translate effortlessly to hold for digraphs too. Another slight adaptation of our work yields related results for (k, l)-split graphs.en_US
dc.description.urihttp://www.springerlink.com/content/0911-0119en_US
dc.identifier.citationBroere, I & Heidema J 2012, 'Universal H-colorable graphs', Graphs and Combinatorics, vol. 29, no. 5, pp. 1193-1206.en_US
dc.identifier.issn0911-0119 (print)
dc.identifier.issn1435-5914 (online)
dc.identifier.other10.1007/s00373-012-1216-5
dc.identifier.urihttp://hdl.handle.net/2263/19830
dc.language.isoenen_US
dc.publisherSpringeren_US
dc.rights© Springer-Verlag 2012. The original publication is available at www.springerlink.com.en_US
dc.subjectUniversal graphen_US
dc.subjectHom-property of graphsen_US
dc.subjectExtension property of graphsen_US
dc.subjectHomogeneous graphen_US
dc.subjectH-colourable graphen_US
dc.subjectk-colourable graphen_US
dc.subject(k, l)-split graphen_US
dc.subjectRado graphen_US
dc.titleUniversal H-colourable graphsen_US
dc.typePostprint Articleen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Broere_Universal(2012).pdf
Size:
168.33 KB
Format:
Adobe Portable Document Format
Description:
Postprint Article

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: