A characterization of edge-ordered graphs with almost linear extremal functions

DOI10.1007/S00493-023-00052-5MaRDI QIDQ6143933zbMATH OpenFDO

Authors Gaurav Kucherlya, Gábor Tardos

Publication date 25 January 2024

Published in Combinatorica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2206.12979

zbMATH Keywords

edge-ordered graphsextremal graph theoryTurán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: The systematic study of Tur'an-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. arXiv:2001.00849. They conjectured that the extremal functions of edge-ordered forests of order chromatic number 2 are $n^{1+o(1)}$. Here we resolve this conjecture proving the stronger upper bound of $n{2}^{O(sqrtlogn)}$. This represents a gap in the family of possible extremal functions as other forbidden edge-ordered graphs have extremal functions $Omega(n^c)$ for some $c>1$. However, our result is probably not the last word: here we conjecture that the even stronger upper bound of $nlo{g}^{O(1)}n$ also holds for the same set of extremal functions.

Review text

Edge-ordered forest denotes an edge-ordered graph with a forest as its underlying simple graph. The authors prove that the extremal function of an edge-ordered graph is almost linear if and only if the graph is an edge-ordered forest of order chromatic number 2. An upper bound is established for the extremal functions of edge-ordered forests of order chromatic number 2.

Recommendations

• Ordered and convex geometric trees with linear extremal function
• Chromatic number of ordered graphs with forbidden ordered subgraphs
• On the Turán number of ordered forests
• On the Turán number of ordered forests

Cited in

(2)

• Tight bounds for intersection-reverse sequences, edge-ordered graphs, and applications
• Saturation of edge-ordered graphs

This page was built for publication: A characterization of edge-ordered graphs with almost linear extremal functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6143933)