Abstract:We prove that if $G=(V,E)$ is a nonprime graph with either no infinite independent set or no infinite clique, then every vertex of $G$ belongs to a maximal strong module distinct from $V$. In particular, $G$ admits a Gallai decomposition.
As a consequence, we obtain that every interval order $P$ with no infinite antichain admits a Gallai decomposition. That is, $P$ is a lexicographical sum of interval orders distinct from $P$ indexed by either a chain, an antichain, or a prime interval order.
Next, we prove that every prime interval order with no infinite antichain is at most countable and does not embed a copy of the chain of rational numbers.
Finally, for each countable ordinal $\alpha$, we construct a well-quasi-ordered prime interval order $P_\alpha$ whose chain of maximal antichains has Hausdorff rank $\alpha$.
From: Imed Zaguia [view email]
[v1]
Mon, 11 Nov 2024 03:27:45 UTC (33 KB)
[v2]
Fri, 5 Jun 2026 23:15:37 UTC (34 KB)
[v3]
Sat, 5 Sep 2026 18:41:22 UTC (38 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。