Hom-properties are uniquely factorizable into irreducible factors (Q1970713)

An additive hereditary property \(P\) of graphs (i.e., a class of graphs closed under isomorphisms, subgraphs, and disjoint unions) is reducible, if there exist properties \(P_1, P_2\), such that a graph \(G\) has property \(P\) if and only if it admits a vertex partition into induced subgraphs \(G_1\) and \(G_2\), where each \(G_i\) has property \(P_i\). In such a case, \(P\) is said to be factored into \(P_1, P_2\). Otherwise, \(P\) is called irreducible. The authors observe that \(H\)-colourability (the property of admitting a homomorphism, i.e., an edge-preserving mapping, to \(H\)) is an additive hereditary property, and characterize graphs \(H\) for which \(H\)-colourability is reducible. They also prove the uniqueness of factoring a reducible \(H\)-colourability property into irreducible additive hereditary properties.