Duality and $χ^<$-Boundedness of Ordered Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914204684910592 |
|---|---|
| author | Čertík, Michal Nešetřil, Jaroslav |
| author_facet | Čertík, Michal Nešetřil, Jaroslav |
| contents | We show that there exists only one duality pair for ordered graphs. We will also define a corresponding definition of $χ^<$-boundedness for ordered graphs and show that all ordered graphs are $χ^<$-bounded and prove an analogy of Gyárfás-Sumner conjecture for ordered graphs. We also prove an analogy of Sparse Incomparability Lemma for ordered graphs. We then use this result to show classes of ordered graphs that form a dense order under ordered homomorphisms. We also show that compared to graphs, ordered graphs have more gaps, defined by consecutive monotone matchings and by even more generic pairs of ordered graphs differing by one isolated edge. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00852 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Duality and $χ^<$-Boundedness of Ordered Graphs Čertík, Michal Nešetřil, Jaroslav Combinatorics We show that there exists only one duality pair for ordered graphs. We will also define a corresponding definition of $χ^<$-boundedness for ordered graphs and show that all ordered graphs are $χ^<$-bounded and prove an analogy of Gyárfás-Sumner conjecture for ordered graphs. We also prove an analogy of Sparse Incomparability Lemma for ordered graphs. We then use this result to show classes of ordered graphs that form a dense order under ordered homomorphisms. We also show that compared to graphs, ordered graphs have more gaps, defined by consecutive monotone matchings and by even more generic pairs of ordered graphs differing by one isolated edge. |
| title | Duality and $χ^<$-Boundedness of Ordered Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.00852 |