Unique factorisation of additive induced-hereditary properties
Alastair Farrugia, R. Bruce Richter · Discussiones Mathematicae Graph Theory · 2004
An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let P1,...,Pn be additive hereditary graph properties. A graph G has property (P1 ◦ · · · ◦ Pn) if there is a partition (V1,...,Vn) of V (G) into n sets such that, for all i, the induced subgraph G[Vi] is in Pi. A property P is reducible if there are properties Q, R such that P = Q ◦ R; otherwise it is irreducible. Mihók, Semaniˇsin and Vasky [J. Graph Theory 33 (2000), 44–53] gave a factorisation for any additive hereditary property P into a given number dc(P) of irreducible additive hereditary factors. Mihók [Discuss. Math. Graph Theory 20 (2000), 143–153] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and The first author’s studies in Canada are fully funded by the Canadian government through a Canadian Commonwealth Scholarship. The second author’s research is financially supported by NSERC. The results presented here form part of the first author’s Ph.D. thesis, that he is writing under the supervision of the second author. 1 disjoint unions). Their results left open the possiblity of different factorisations, maybe even with a different number of factors; we prove here that the given factorisations are, in fact, unique. 1