The property of k-colourable graphs is uniquely decomposable
Loading...
Date
Authors
Broere, Izak
Dorfling, Michael J.
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Abstract
An additive hereditary graph property is a class of simple graphs which is closed
under unions, subgraphs and isomorphisms. If P1; : : : ;Pn are graph properties,
then a (P1; : : : ;Pn)-decomposition of a graph G is a partition E1; : : : ;En of
E(G) such that G[Ei], the subgraph of G induced by Ei, is in Pi, for i = 1; : : : ; n.
The sum of the properties P1; : : : ;Pn is the property P1 Pn = fG 2 I :
G has a (P1; : : : ;Pn)-decompositiong. A property P is said to be decomposable
if there exist non-trivial additive hereditary properties P1 and P2 such that
P = P1 P2. 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 Ok is a uniquely decomposable property.
Keywords: graph property, decomposable property
Description
Keywords
Graph property, Decomposable property
Sustainable Development Goals
Citation
Broere, I & Dorfling, MJ 2013, 'The property of k-colourable graphs is uniquely decomposable', Discrete Mathematics, vol. 313, no. 19, pp. 1961-1964.