Banner not found
Concepts
Open problems

Main concepts

 

The notion of hereditary property of graphs have been mentioned already in the book of Frank Harary in 1969.

The hereditary properties of graphs were investigated in connection with generalization of the basic graph-theoretical invariants as chromatic number, achromatic number, arboricity, vertex and edge independence (covering) number, etc.
Several paper on hereditary properties of graphs appeared in 1972-1973 by S.T. Hedetniemi, E.J. Cockayne, G.G. Miller, G. Prins, J.R. Jones.
Let us recall the definition of the concept given in these papers:

"Let S be a finite set and suppose that P is a property associated with the subsets of S. If T (a subset of S) has property P, we say that T is a P-set. A property P is called hereditary if each subset of a P-set is also a P-set."
E.J. Cockayne, G.G. Miller and G. Prins, An interpolatation Theorem for partitions which are complete with respect to hereditary properties, J. Comb. Theory (B) 13 (1972) 290-297.

"Let P denote any property of a graph G; P is said to be hereditary if whenever a graph G has property P and H is a subgraph of G, then H also has property P. Examples of hereditary properties of graphs are numerous: to be totally disconnected, to be planar etc."
"The property that a graph is complete is not hereditary. However every induced subgraph of a complete graph is complete. A property P of a graph G is an induced hereditary property if whenever G has property P and H is an induced subgraph of G, than also H has property P."

S.T. Hedetniemi, On hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 94-99.

The structure of hereditary properties of graphs and size of hereditary classes have been investigated by V.E. Alekseev, B. Bollobás, E.R. Scheinerman, A. Thomason, and J. Zito and others (see B. Bollobás and A. Thomason, Hereditary and Monotone Properties of Graphs, The mathematics of Paul Erdos II. Springer Verlag 1997, 70-78.

Generalization of regular colourings with respect to hereditary properties of graphs were investigated by B. Bollobás, M. Borowiecki, I. Broere, J.I. Brown, D. Corneil, M. Frick, P. Mihók, A. Thomason, D. West, D. Woodall and others (see M. Borowiecki, I. Broere, M. Frick, P. Mihók, G. Semanišin, Survey of hereditary properties of graphs, Discussiones Mathematicae - Graph Theory 17 (1997) 5-50.

Bulletin

22. September 2017

Rafal Kalinowski was elected to the presidency of the Hereditarnia Club. 

1. January 2017

Wilfried Imrich took the president office of Hereditarnia Club. 

17. May 2012

The memorial seminar Hereditarnia of Peter Mihók was held on May 17th 2012.

27. March 2012

We regret to announce that our friend Peter Mihók, one of the founder members of Hereditarnia Club, passed away at the age of 62 after a long illness.