Factorisations and characterisations of induced-hereditary and compositive properties
| dc.creator | Farrugia, A. | |
| dc.creator | Richter, R. Bruce | |
| dc.creator | Semanisin, G. | |
| dc.date | 2003-08-05 | |
| dc.date.accessioned | 2026-07-07T05:00:09Z | |
| dc.date.available | 2026-07-07T05:00:09Z | |
| dc.description | A graph property (i.e., a set of graphs) is induced-hereditary or additive if it is closed under taking induced-subgraphs or disjoint unions. If $\cP$ and $\cQ$ are properties, the product $\cP \circ \cQ$ consists of all graphs $G$ for which there is a partition of the vertex set of $G$ into (possibly empty) subsets $A$ and $B$ with $G[A] \in \cP$ and $G[B] \in \cQ$. A property is reducible if it is the product of two other properties, and irreducible otherwise. We completely describe the few reducible induced-hereditary properties that have a unique factorisation into irreducibles. Analogs of compositive and additive induced-hereditary properties are introduced and characterised in the style of Scheinerman [{\em Discrete Math}. {\bf 55} (1985) 185--193]. One of these provides an alternative proof that an additive hereditary property factors into irreducible additive hereditary properties. | |
| dc.description | 19 pages, submitted to Journal of Graph Theory | |
| dc.identifier | https://arxiv.org/abs/math/0308045 | |
| dc.identifier | http://arxiv.org/abs/math/0308045 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68254 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15, 05C99 | |
| dc.title | Factorisations and characterisations of induced-hereditary and compositive properties | |
| dc.type | text |