Abstract | ||
---|---|---|
An antichain A of a well-founded quasi-order Q is canonical if for every ideal F of Q, F has an infinite antichain if and only if F@?A is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.disc.2007.12.018 | Discrete Mathematics |
Keywords | Field | DocType |
subgraph,infinite antichain,well-quasi-ordering,induced subgraph | Discrete mathematics,Graph,Combinatorics,Antichain,Induced subgraph,If and only if,Well-quasi-ordering,Mathematics | Journal |
Volume | Issue | ISSN |
309 | 5 | Discrete Mathematics |
Citations | PageRank | References |
4 | 0.43 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Guoli Ding | 1 | 444 | 51.58 |