Unique factorisation of additive induced-hereditary properties

Simple item page
dc.creatorFarrugia, Alastair
dc.creatorRichter, R. Bruce
dc.date2003-06-10
dc.date.accessioned2026-07-07T04:58:43Z
dc.date.available2026-07-07T04:58:43Z
dc.descriptionAn additive hereditary graph property is a set of graphs, closed under isomorphism and under taking subgraphs and disjoint unions. Let ${\cal P}_1, >..., {\cal P}_n$ be additive hereditary graph properties. A graph $G$ has property $({\cal P}_1 \circ ... \circ {\cal P}_n)$ if there is a partition $(V_1, ..., V_n)$ of $V(G)$ into $n$ sets such that, for all $i$, the induced subgraph $G[V_i]$ is in ${\cal P}_i$. A property ${\cal P}$ is reducible if there are properties ${\cal Q}$, ${\cal R}$ such that ${\cal P} = {\cal Q} \circ {\cal R}$; otherwise it is irreducible. Mihók, Semanišin and Vasky [J. Graph Theory {\bf 33} (2000), 44--53] gave a factorisation for any additive hereditary property ${\cal P}$ into a given number $dc({\cal P})$ of irreducible additive hereditary factors. Mihók [Discuss. Math. Graph Theory {\bf 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.
dc.description26 pages, 4 figures, to appear in Discussiones Mathematicae Graph Theory
dc.identifierhttps://arxiv.org/abs/math/0306165
dc.identifierhttp://arxiv.org/abs/math/0306165
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/67754
dc.subjectCombinatorics
dc.subject05C15 (Primary), 05C62, 05C75 (Secondary)
dc.titleUnique factorisation of additive induced-hereditary properties
dc.typetext

Files

Collections

arXiv