Universality in Graph Properties with Degree Restrictions

Izak Broere; Johannes Heidema; Peter Mihók

Discussiones Mathematicae Graph Theory (2013)

  • Volume: 33, Issue: 3, page 477-492
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Izak Broere, Johannes Heidema, and Peter Mihók. "Universality in Graph Properties with Degree Restrictions." Discussiones Mathematicae Graph Theory 33.3 (2013): 477-492. <http://eudml.org/doc/268159>.

@article{IzakBroere2013,
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 [...] 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.},
author = {Izak Broere, Johannes Heidema, Peter Mihók},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {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 },
language = {eng},
number = {3},
pages = {477-492},
title = {Universality in Graph Properties with Degree Restrictions},
url = {http://eudml.org/doc/268159},
volume = {33},
year = {2013},
}

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
VL - 33
IS - 3
SP - 477
EP - 492
AB - 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.
LA - eng
KW - 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
UR - http://eudml.org/doc/268159
ER -

References

top
  1. [1] M. Borowiecki, I. Broere, M. Frick, G. Semanišin and P. Mihók, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50. doi:10.7151/dmgt.1037[Crossref] Zbl0902.05026
  2. [2] I. Broere and J. Heidema, Some universal directed labelled graphs, Util. Math. 84 (2011) 311-324. Zbl1228.05250
  3. [3] I. Broere and J. Heidema, Universal H-colourable graphs, Graphs Combin., accepted for publication. doi:10.1007/s00373-012-1216-5[Crossref] Zbl1272.05136
  4. [4] I. Broere, J. Heidema and P. Mihók, Constructing universal graphs for inducedhereditary graph properties, Math. Slovaca 63 (2013) 191-200. doi:10.7151/s12175-012-0092-z[Crossref][WoS] Zbl1324.05135
  5. [5] G. Cherlin and P. Komjáth, There is no universal countable pentagon-free graph, J. Graph Theory 18 (1994) 337-341. doi:10.1002/jgt.3190180405[Crossref] Zbl0805.05044
  6. [6] G. Cherlin and N. Shi, Graphs omitting a finite set of cycles, J. Graph Theory 21 (1996) 351-355. doi:10.1002/(SICI)1097-0118(199603)21:3h351::AID-JGT11i3.0.CO;2-K[Crossref] Zbl0845.05060
  7. [7] R. Diestel, Graph theory (Fourth Edition, Graduate Texts in Mathematics, 173; Springer, Heidelberg, 2010). Zbl1204.05001
  8. [8] P. Erdös and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Hungar. 17 (1966) 61-99. doi:10.1007/BF02020444[Crossref] 
  9. [9] L. Esperet, A. Labourel and P. Ochem, On induced-universal graphs for the class of bounded-degree graphs, Inform. Process. Lett. 108 (2008) 255-260. doi:10.1016/j.ipl.2008.04.020[Crossref][WoS] Zbl1189.05162
  10. [10] R. Fraïssé, Sur l’extension aux relations de quelques propriétiés connues des ordres, C. R. Acad. Sci. Paris 237 (1953) 508-510. Zbl0053.02904
  11. [11] Z. Füredi and P. Komjáth, On the existence of countable universal graphs, J. Graph Theory 25 (1997) 53-58. doi:10.1002/(SICI)1097-0118(199705)25:1h53::AID-JGT3i3.0.CO;2-H[Crossref] 
  12. [12] A. Hajnal and J. Pach, Monochromatic paths in infinite coloured graphs, Finite and infinite sets, Colloquia Mathematica Societatis János Bolyai, Eger, Hungary 37 (1981) 359-369. 
  13. [13] C.W. Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971) 69-83. doi:10.2140/pjm.1971.38.69[Crossref] 
  14. [14] P. Komjáth and J. Pach, Universal graphs without large bipartite subgraphs, Mathematika 31 (1984) 282-290. doi:10.1112/S002557930001250X[Crossref] Zbl0551.05057
  15. [15] D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096. doi:10.4153/CJM-1970-125-1[Crossref] Zbl0202.23502
  16. [16] P. Mihók, J. Miškuf and G. Semanišin, On universal graphs for hom-properties, Discuss. Math. Graph Theory 29 (2009) 401-409. doi:10.7151/dmgt.1455[Crossref] Zbl1194.05041
  17. [17] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964) 331-340. Zbl0139.17303

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.