HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Finiteness Theorems for Graphs and Posets Obtained by Compositions

Jens Gustedt 1
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it. In particular we show that the following classes have infiniteantichains with resp. to the induced subgraph/poset relation : interval graphs and orders, $N$-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.
Document type :
Journal articles
Complete list of metadata

Contributor : Jens Gustedt Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:38:54 AM
Last modification on : Friday, February 4, 2022 - 3:30:59 AM


  • HAL Id : inria-00098825, version 1



Jens Gustedt. Finiteness Theorems for Graphs and Posets Obtained by Compositions. Order, Springer Verlag, 1999, 15 (3), pp.203-220. ⟨inria-00098825⟩



Record views