---
res:
bibo_abstract:
- "An ordered graph is a graph with a linear ordering on its vertex set. We prove
that for every positive integer k, there exists a constant ck > 0 such that any
ordered graph G on n vertices with the property that neither G nor its complement
contains an induced monotone path of size k, has either a clique or an independent
set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and
Thomassé, who proved the analogous result for unordered graphs.\r\nA key idea
of the above paper was to show that any unordered graph on n vertices that does
not contain an induced path of size k, and whose maximum degree is at most c(k)n
for some small c(k) > 0, contains two disjoint linear size subsets with no edge
between them. This approach fails for ordered graphs, because the analogous statement
is false for k ≥ 3, by a construction of Fox. We provide some further examples
showing that this statement also fails for ordered graphs avoiding other ordered
trees.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: János
foaf_name: Pach, János
foaf_surname: Pach
foaf_workInfoHomepage: http://www.librecat.org/personId=E62E3130-B088-11EA-B919-BF823C25FEA4
- foaf_Person:
foaf_givenName: István
foaf_name: Tomon, István
foaf_surname: Tomon
bibo_doi: 10.1016/j.jctb.2021.05.004
bibo_volume: 151
dct_date: 2021^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/00958956
dct_language: eng
dct_publisher: Elsevier@
dct_title: Erdős-Hajnal-type results for monotone paths@
...