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
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.app.ist.ac.at/record/9602
https://research-explorer.app.ist.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/00958956
https://creativecommons.org/licenses/by/4.0/
info:eu-repo/semantics/openAccess