PDF
Discussiones Mathematicae Graph Theory 24(2) (2004)
319-343
DOI: https://doi.org/10.7151/dmgt.1234
UNIQUE FACTORISATION OF ADDITIVE INDUCED-HEREDITARY PROPERTIES
Alastair Farrugia and R. Bruce Richter
Department of Combinatorics and Optimization
University of Waterloo
Ontario, Canada, N2L 3G1
e-mail: afarrugia@math.uwaterloo.ca
e-mail: brichter@math.uwaterloo.ca
Abstract
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šin and Vasky [8] gave a factorisation for any additive hereditary property P into a given number dc(P) of irreducible additive hereditary factors. Mihók [7] gave a similar factorisation for properties that are additive and induced-hereditary (closed under taking induced-subgraphs and 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.Keywords: additive and hereditary graph classes, unique factorization.
2000 Mathematics Subject Classification: 05C70.
References
[1] | I. Broere and J. Bucko, Divisibility in additive hereditary properties and uniquely partitionable graphs, Tatra Mt. Math. Publ. 18 (1999) 79-87. |
[2] | I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discuss. Math. Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038. |
[3] | A. Farrugia, Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard, submitted. |
[4] | A. Farrugia and R.B. Richter, Complexity, uniquely partitionable graphs and unique factorisation, in preparation. www.math.uwaterloo.ca/∼afarrugia/ |
[5] | A. Farrugia and R.B. Richter, Unique factorisation of induced-hereditary disjoint compositive properties, Research Report CORR 2002-ZZ (2002) Department of Combinatorics and Optimization, University of Waterloo. www.math.uwaterloo.ca/~afarrugia/ |
[6] | J. Kratochvil and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors, Discrete Math. 213 (2000) 189-194, doi: 10.1016/S0012-365X(99)00179-X. |
[7] | P. Mihók, Unique Factorization Theorem, Discuss. Math. Graph Theory 20 (2000) 143-153, doi: 10.7151/dmgt.1114. |
[8] | P. Mihók, G. Semanišin and R. Vasky, Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O. |
[9] | G. Semanišin, On generating sets of hereditary properties, unpublished manuscript. |
[10] | J. Szigeti and Zs. Tuza, Generalized colorings and avoidable orientations, Discuss. Math. Graph Theory 17 (1997) 137-146, doi: 10.7151/dmgt.1047. |
Received 6 November 2002
Revised 24 January 2003
Close