Universality in Graph Properties with Degree Restrictions
Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 477.

Voir la notice de l'article dans European Digital Mathematics Library

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.
Classification : 05C63
Mots-clés : countable graph, universal graph, induced-hereditary, k-degenerate graph, graph with colouring number at most k + 1, graph property with assignment, -degenerate graph, graph with colouring number at most 
@article{DMGT_2013__33_3_268159,
     author = {Izak Broere and Johannes Heidema and Peter Mih\'ok},
     title = {Universality in {Graph} {Properties} with {Degree} {Restrictions}},
     journal = {Discussiones Mathematicae Graph Theory},
     pages = {477},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     zbl = {1274.05334},
     language = {en},
     url = {https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268159/}
}
TY  - JOUR
AU  - Izak Broere
AU  - Johannes Heidema
AU  - Peter Mihók
TI  - Universality in Graph Properties with Degree Restrictions
JO  - Discussiones Mathematicae Graph Theory
PY  - 2013
SP  - 477
VL  - 33
IS  - 3
PB  - mathdoc
UR  - https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268159/
LA  - en
ID  - DMGT_2013__33_3_268159
ER  - 
%0 Journal Article
%A Izak Broere
%A Johannes Heidema
%A Peter Mihók
%T Universality in Graph Properties with Degree Restrictions
%J Discussiones Mathematicae Graph Theory
%D 2013
%P 477
%V 33
%N 3
%I mathdoc
%U https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268159/
%G en
%F DMGT_2013__33_3_268159
Izak Broere; Johannes Heidema; Peter Mihók. Universality in Graph Properties with Degree Restrictions. Discussiones Mathematicae Graph Theory, Tome 33 (2013) no. 3, p. 477. https://geodesic-test.mathdoc.fr/item/DMGT_2013__33_3_268159/