The property of k-colourable graphs is uniquely decomposable

Show simple item record Broere, Izak Dorfling, Michael J. 2013-04-16T11:12:10Z 2013-04-16T11:12:10Z 2013-10
dc.description.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 en_US
dc.description.librarian hb2013 en_US
dc.description.uri en_US
dc.identifier.citation Broere, I & Dorfling, MJ 2013, 'The property of k-colourable graphs is uniquely decomposable', Discrete Mathematics, vol. 313, no. 19, pp. 1961-1964. en_US
dc.identifier.issn 0012-365X (print)
dc.identifier.issn 1872-681X (online)
dc.identifier.other 10.1016/j.disc.2012.10.009
dc.language.iso en en_US
dc.publisher Elsevier en_US
dc.rights © 2012 Elsevier Ltd. All rights reserved. Notice : this is the author’s version of a work that was accepted for publication in Discrete Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Mathematics, NYP. en_US
dc.subject Graph property en_US
dc.subject Decomposable property en_US
dc.title The property of k-colourable graphs is uniquely decomposable en_US
dc.type Postprint Article en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record