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

Voir la notice de l'article provenant de la source Library of Science

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 lt; 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 ℐc of all countable graphs (since every graph in ℐc is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of ℐ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.
Keywords: countable graph, universal graph, induced-hereditary, k-degenerate graph, graph with colouring number at most k + 1, graph property with assignment 
@article{DMGT_2013_33_3_a0,
     author = {Broere, Izak and Heidema, Johannes and Mih\'ok, Peter},
     title = {Universality in {Graph} {Properties} with {Degree} {Restrictions}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {477--492},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/}
}
TY  - JOUR
AU  - Broere, Izak
AU  - Heidema, Johannes
AU  - Mihók, Peter
TI  - Universality in Graph Properties with Degree Restrictions
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2013
SP  - 477
EP  - 492
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/
LA  - en
ID  - DMGT_2013_33_3_a0
ER  - 
%0 Journal Article
%A Broere, Izak
%A Heidema, Johannes
%A Mihók, Peter
%T Universality in Graph Properties with Degree Restrictions
%J Discussiones Mathematicae. Graph Theory
%D 2013
%P 477-492
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/
%G en
%F DMGT_2013_33_3_a0
Broere, Izak; Heidema, Johannes; Mihók, Peter. Universality in Graph Properties with Degree Restrictions. Discussiones Mathematicae. Graph Theory, Tome 33 (2013) no. 3, pp. 477-492. http://geodesic.mathdoc.fr/item/DMGT_2013_33_3_a0/