Prime ideals in the lattice of additive induced-hereditary graph properties

Amelie J. Berger; Peter Mihók

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 1, page 117-127
  • ISSN: 2083-5892

Abstract

top
An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.

How to cite

top

Amelie J. Berger, and Peter Mihók. "Prime ideals in the lattice of additive induced-hereditary graph properties." Discussiones Mathematicae Graph Theory 23.1 (2003): 117-127. <http://eudml.org/doc/270178>.

@article{AmelieJ2003,
abstract = {An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.},
author = {Amelie J. Berger, Peter Mihók},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary graph property; prime ideal; distributive lattice; induced subgraphs},
language = {eng},
number = {1},
pages = {117-127},
title = {Prime ideals in the lattice of additive induced-hereditary graph properties},
url = {http://eudml.org/doc/270178},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Amelie J. Berger
AU - Peter Mihók
TI - Prime ideals in the lattice of additive induced-hereditary graph properties
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 1
SP - 117
EP - 127
AB - An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.
LA - eng
KW - hereditary graph property; prime ideal; distributive lattice; induced subgraphs
UR - http://eudml.org/doc/270178
ER -

References

top
  1. [1] A. Berger, I. Broere, P. Mihók and S. Moagi, Meet- and join-irreducibility of additive hereditary properties of graphs, Discrete Math. 251 (2002) 11-18, doi: 10.1016/S0012-365X(01)00323-5. Zbl1003.05101
  2. [2] 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
  3. [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68. 
  4. [4] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M. Mislove and D.S. Scott, A Compendium of Continuous Lattices (Springer-Verlag, 1980). Zbl0452.06001
  5. [5] G. Grätzer, General Lattice Theory (Second edition, Birkhäuser Verlag, Basel, Boston, Berlin 1998). Zbl0909.06002
  6. [6] J. Jakubík, On the lattice of additive hereditary properties of finite graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86. Zbl1032.06003
  7. [7] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
  8. [8] E.R. Scheinerman, Characterizing intersection classes of graphs, Discrete Math. 55 (1985) 185-193, doi: 10.1016/0012-365X(85)90047-0. Zbl0597.05056
  9. [9] E.R. Scheinerman, On the structure of hereditary classes of graphs, J. Graph Theory 10 (1986) 545-551. Zbl0609.05057

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.