Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties

Ewa Drgas-Burchardt

Discussiones Mathematicae Graph Theory (2009)

  • Volume: 29, Issue: 2, page 263-274
  • ISSN: 2083-5892

Abstract

top
An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let L a denote a class of all such properties. In the paper, we consider H-reducible over L a properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.

How to cite

top

Ewa Drgas-Burchardt. "Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties." Discussiones Mathematicae Graph Theory 29.2 (2009): 263-274. <http://eudml.org/doc/270353>.

@article{EwaDrgas2009,
abstract = {An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.},
author = {Ewa Drgas-Burchardt},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary graph property; lattice of additive hereditary graph properties; minimal forbidden graph family; join in the lattice; reducibility},
language = {eng},
number = {2},
pages = {263-274},
title = {Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties},
url = {http://eudml.org/doc/270353},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Ewa Drgas-Burchardt
TI - Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 2
SP - 263
EP - 274
AB - An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let $L^a$ denote a class of all such properties. In the paper, we consider H-reducible over $L^a$ properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
LA - eng
KW - hereditary graph property; lattice of additive hereditary graph properties; minimal forbidden graph family; join in the lattice; reducibility
UR - http://eudml.org/doc/270353
ER -

References

top
  1. [1] A.J. Berger, Minimal forbidden subgraphs of reducible graph properties, Discuss. Math. Graph Theory 21 (2001) 111-117, doi: 10.7151/dmgt.1136. Zbl0989.05060
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (North-Holland, New York, 1981). Zbl1226.05083
  3. [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishawa International Publication, Gulbarga, 1991) 41-68. 
  4. [4] M. Borowiecki, I. Broere, M. Frick, P.Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. Zbl0902.05026
  5. [5] E.J. Cockayne, Colour classes for r-graphs, Canad. Math. Bull. 15 (1972) 349-354, doi: 10.4153/CMB-1972-063-2. Zbl0254.05106
  6. [6] E. Drgas-Burchardt, On uniqueness of a general factorization of graph properties, submitted. 
  7. [7] E. Drgas-Burchardt, A note on joins of additive hereditary graph properties, Discuss. Math. Graph Theory 26 (2006) 413-418, doi: 10.7151/dmgt.1333. 
  8. [8] M. Frick, A survey of (m,k)-colorings, in: J. Gimbel et al. (Eds), Quo Vadis Graph Theory? A source book for challenges and directions, Annals Discrete Math. 55 (North-Holland, Amsterdam, 1993) 45-57, doi: 10.1016/S0167-5060(08)70374-1. 
  9. [9] D.L. Greenwell, R.L. Hemminger and J. Klerlein, Forbidden subgraphs, in: Proceedings of the 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man., 1973) 389-394. Zbl0312.05128
  10. [10] G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952) 326-336, doi: 10.1112/plms/s3-2.1.326. Zbl0047.03402
  11. [11] J. Jakubik, On the Lattice of Additive Hereditary Properties of Finite Graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86. Zbl1032.06003
  12. [12] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q. 
  13. [13] N. Robertson and P.D. Seymour, Graph minors - a survey, in: Surveys in Combinatorics 1985 (Glasgow, 1985), London Math. Soc. Lecture Note Ser. 103 (Cambridge University Press., Cambridge 1985), 153-171. 

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.