Paper Info
Title
Universality in graph properties with degree restrictions.
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 I-c of all countable graphs (since every graph in I-c is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of I-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.
Year
DOI
Venue
2013
10.7151/dmgt.1696
DISCUSSIONES MATHEMATICAE GRAPH THEORY
Keywords
Field
DocType
countable graph,universal graph,induced-hereditary,k-degenerate graph,graph with colouring number at most k+1,graph property with assignment
Discrete mathematics,Combinatorics,Line graph,Vertex-transitive graph,Distance-hereditary graph,Factor-critical graph,Symmetric graph,Universal graph,Voltage graph,Mathematics,Complement graph
Journal
Volume
Issue
ISSN
33
3
1234-3099
Citations 
PageRank 
References 
0
0.34
6
Authors
3
Name
Order
Citations
PageRank
Izak Broere114331.30
Johannes Heidema2306.96
Peter Mihók323244.49