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

Discussiones Mathematicae Graph Theory (2003)

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

## Access Full Article

top## Abstract

top## How to cite

topAmelie 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] 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] 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] 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] 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] G. Grätzer, General Lattice Theory (Second edition, Birkhäuser Verlag, Basel, Boston, Berlin 1998). Zbl0909.06002
- [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] T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
- [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] E.R. Scheinerman, On the structure of hereditary classes of graphs, J. Graph Theory 10 (1986) 545-551. Zbl0609.05057