Premium
On structural descriptions of lower ideals of trees
Author(s) -
Nigussie Yared,
Robertson Neil
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20105
Subject(s) - axiom , mathematics , uniqueness , constructive , set (abstract data type) , graph , discrete mathematics , combinatorics , computer science , geometry , mathematical analysis , process (computing) , programming language , operating system
A finite structural description for proper lower ideals of trees was found in [5] by Robertson, Seymour, and Thomas. They proved existence of a specific description satisfying three axioms. We present our result starting from this fundamental construction. In an attempt to make their description unique and efficient, they introduced a fourth axiom, which conflicts with one of the prior axioms. In this paper, we make use of their valid constructive result and prove the desired uniqueness and efficiency using a different set of axioms. © 2005 Wiley Periodicals, Inc. J Graph Theory