Bounds on half graph orders in powers of sparse graphs
From MaRDI portal
Publication:6362595
DOI10.37236/11063arXiv2103.06218MaRDI QIDQ6362595
Publication date: 10 March 2021
Abstract: Half graphs and their variants, such as ladders, semi-ladders and co-matchings, are combinatorial objects that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb.; 2014) and Fabia'nski et al. (STACS; 2019) prove that in the powers of sparse graphs, one cannot find arbitrarily large objects of this kind. However, these proofs either are non-constructive, or provide only loose upper bounds on the orders of half graphs and semi-ladders. In this work we provide nearly tight asymptotic lower and upper bounds on the maximum order of half graphs, parameterized on the distance, in the following classes of sparse graphs: planar graphs, graphs with bounded maximum degree, graphs with bounded pathwidth or treewidth, and graphs excluding a fixed clique as a minor. The most significant part of our work is the upper bound for planar graphs. Here, we employ techniques of structural graph theory to analyze semi-ladders in planar graphs through the notion of cages, which expose a topological structure in semi-ladders. As an essential building block of this proof, we also state and prove a new structural result, yielding a fully polynomial bound on the neighborhood complexity in the class of planar graphs.
Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Density (toughness, etc.) (05C42)
This page was built for publication: Bounds on half graph orders in powers of sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6362595)
