DMGT

Discussiones Mathematicae Graph Theory 23(1) (2003) 117-127
DOI: https://doi.org/10.7151/dmgt.1189

PRIME IDEALS IN THE LATTICE OF ADDITIVE INDUCED-HEREDITARY GRAPH PROPERTIES

Amelie J. Berger

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa
e-mail: abe@raua.rau.ac.za

Peter Mihók

Departement of Applied Mathematics and Informatics
Faculty of Economics, University of Technology
B. Nemcovej 32, 040 02 Košice, Slovakia
and
Mathematical Institute of Slovak Academy of Sciences
Gresákova 6, 040 01 Košice, Slovakia
e-mail: Peter.Mihok@tuke.sk

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.

Keywords: hereditary graph property, prime ideal, distributive lattice, induced subgraphs

2000 Mathematics Subject Classification: 05C99, 06B10, 06D10.

References

[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.
[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.
[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).
[5]	G. Grätzer, General Lattice Theory (Second edition, Birkhäuser Verlag, Basel, Boston, Berlin 1998).
[6]	J. Jakubík, On the lattice of additive hereditary properties of finite graphs, Discuss. Math. General Algebra and Applications 22 (2002) 73-86.
[7]	T.R. Jensen and B. Toft, Graph Colouring Problems (Wiley-Interscience Publications, New York, 1995).
[8]	E.R. Scheinerman, Characterizing intersection classes of graphs, Discrete Math. 55 (1985) 185-193, doi: 10.1016/0012-365X(85)90047-0.
[9]	E.R. Scheinerman, On the structure of hereditary classes of graphs, J. Graph Theory 10 (1986) 545-551.

Received 12 July 2001
Revised 29 July 2002