Hereditary properties of graphs Original Research Article

A property P of graphs is said to be hereditary if whenever a graph G has the property P and H is an induced subgraph of G, then H also has this property P. Two hereditary properties P1, P2 are said to be equivalent if G(P1)=G(P2), where for i=1,2 the set of all graphs which have the property Pi is denoted by G(Pi). A hereditary property P is said to be reducible if there exist two hereditary properties P1 and P2, neither being equivalent to P such that G(P)=G(P1) ∪ G(P2), in which case the property P is said to be the union of P1 and P2 and is denoted by P1∨P2; P is irreducible otherwise. In this paper we characterize irreducible properties and disprove the following conjecture raised by Rao: If P is a hereditary property, then there exist finitely many irreducible properties P1,P2,…,Pn such that P=P1∨P2∨⋯∨Pn