The Aharoni--Korman conjecture for $N$-free posets with no infinite antichain
| Autor: | Zaguia, Imed |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We give a necessary and sufficient condition for a $P_4$-free graph to be a cograph. This allows us to obtain a simple proof of the fact that finite $P_4$-free graphs are finite cographs. We also prove that $N$-free chain complete posets and $N$-free posets with no infinite antichains are series-parallel. As a consequence, we obtain that every $N$-free poset with no infinite antichain has a chain and a partition into antichains so that each part intersects the chain. This answers a conjecture of Aharoni and Korman (Order \textbf{9} (1992) 245--253) in this case. Comment: 9 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|