Erdős-Hajnal-type results for monotone paths Pach, János Tomon, István ddc:510 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. A 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. Elsevier 2021 info:eu-repo/semantics/article doc-type:Article Article http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/9602 https://research-explorer.ista.ac.at/download/9602/9612 Pach J, Tomon I. Erdős-Hajnal-type results for monotone paths. <i>Journal of Combinatorial Theory Series B</i>. 2021;151:21-37. doi:<a href="https://doi.org/10.1016/j.jctb.2021.05.004">10.1016/j.jctb.2021.05.004</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jctb.2021.05.004 info:eu-repo/semantics/altIdentifier/issn/0095-8956 info:eu-repo/semantics/altIdentifier/wos/000702280800002 info:eu-repo/semantics/openAccess