| Autor: |
Broere Izak, Heidema Johannes, Mihók Peter |
| Jazyk: |
angličtina |
| Rok vydání: |
2013 |
| Předmět: |
|
| Zdroj: |
Discussiones Mathematicae Graph Theory, Vol 33, Iss 3, Pp 477-492 (2013) |
| Druh dokumentu: |
article |
| ISSN: |
2083-5892 |
| DOI: |
10.7151/dmgt.1696 |
| Popis: |
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 of all countable graphs (since every graph in is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of 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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
