Unique factorisation of additive induced-hereditary properties

DOI10.7151/DMGT.1234MaRDI QIDQ4669437zbMATH OpenOpenAlexFDO

Authors Alastair Farrugia, R. B. Richter

Publication date 15 April 2005

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0306165

zbMATH Keywords

additive and hereditary graph classes

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: An additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ${calP}_1,>\mathrm{...},{calP}_n$ be additive hereditary graph properties. A graph $G$ has property $({calP}_{1}circ\mathrm{...}circ{calP}_n)$ if there is a partition $(V_1,\mathrm{...},V_n)$ of $V(G)$ into $n$ sets such that, for all $i$, the induced subgraph $G[V_i]$ is in ${calP}_i$. A property $calP$ is reducible if there are properties $calQ$, $calR$ such that $calP=calQcirccalR$; otherwise it is irreducible. Mih'{o}k, Semaniv{s}in and Vasky [J. Graph Theory {�f 33} (2000), 44--53] gave a factorisation for any additive hereditary property $calP$ into a given number $dc(calP)$ of irreducible additive hereditary factors. Mih'{o}k [Discuss. Math. Graph Theory {�f 20} (2000), 143--153] 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.

Recommendations

• Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
• Unique factorization theorem
• Factorizations and characterizations of induced‐hereditary and compositive properties
• scientific article; zbMATH DE number 2109749
• Hom-properties are uniquely factorizable into irreducible factors

Cited in

(11)

• Minimal reducible bounds for induced-hereditary properties
• Hom-properties are uniquely factorizable into irreducible factors
• Unique factorization of compositive hereditary graph properties
• On uniqueness of a general factorization of graph properties
• Prime ideals in the lattice of additive induced-hereditary graph properties
• Unique factorization theorem
• Factorizations and characterizations of induced‐hereditary and compositive properties
• On generating sets of induced-hereditary properties
• scientific article; zbMATH DE number 2109749 (Why is no real title available?)
• Additive and hereditary properties of graphs are uniquely factorizable into irreducible factors
• Unique Factorization Theorem and Formal Concept Analysis

This page was built for publication: Unique factorisation of additive induced-hereditary properties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4669437)