Paper Info
Title
Universal H-Colourable Graphs
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 $${\mathcal{I}_c}$$ of all countable graphs (since every graph in $${\mathcal{I}_c}$$ 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 graph U ( H ) which is H -universal in H c , 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 K k , then H c 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 H c which is H -homogeneous in H c . The graphs H for which $${U(H) \cong 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.
Year
DOI
Venue
2013
10.1007/s00373-012-1216-5
Graphs and Combinatorics
Keywords
Field
DocType
k-colourable graph,extension property of graphs,universal graph,-split graph,h-colourable graph,rado graph,05c63,homogeneous graph,hom-property of graphs
Random regular graph,Topology,Discrete mathematics,Combinatorics,Vertex-transitive graph,Graph isomorphism,Forbidden graph characterization,Graph homomorphism,Symmetric graph,Universal graph,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
29
5
1435-5914
Citations 
PageRank 
References 
0
0.34
2
Authors
2
Name
Order
Citations
PageRank
Izak Broere114331.30
Johannes Heidema2306.96