The property of -colourable graphs is uniquely decomposable

An additive hereditary graph property is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If P 1 , … , P n are graph properties, then a ( P 1 , … , P n ) -decomposition of a graph G is a partition E 1 , … , E n of E ( G ) such that G [ E i ] , the subgraph of G induced by E i , is in P i , for i = 1 , … , n . The sum of the properties P 1 , … , P n is the property P 1 ⊕ ⋯ ⊕ P n = { G ∈ I : G  has a  ( P 1 , … , P n ) -decomposition } . A property P is said to be decomposable if there exist non-trivial additive hereditary properties P 1 and P 2 such that P = P 1 ⊕ P 2 . A property is uniquely decomposable if, apart from the order of the factors, it can be written as a sum of indecomposable properties in only one way. We show that not all properties are uniquely decomposable; however, the property of k -colourable graphs O k is a uniquely decomposable property.