Geodesic
Bounds on half graph orders in powers of sparse graphs
Marek Sokołowski1
1Institute of Informatics, University of Warsaw
The electronic journal of combinatorics, Tome 30 (2023) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Half graphs and their variants, such as semi-ladders and co-matchings, are configurations that encode total orders in graphs. Works by Adler and Adler (Eur. J. Comb.; 2014) and Fabiański et al. (STACS; 2019) prove that in powers of sparse graphs, one cannot find arbitrarily large configurations 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 by the power, 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 via 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.
DOI : 10.37236/11063
Classification : 05C42, 05C12, 05C35, 05C75
Mots-clés : upper bound for planar graphs, semi-ladders in planar graphs, cages

Marek Sokołowski  1

1 Institute of Informatics, University of Warsaw 
@article{10_37236_11063,
     author = {Marek Soko{\l}owski},
     title = {Bounds on half graph orders in powers of sparse graphs},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {2},
     doi = {10.37236/11063},
     zbl = {1511.05120},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11063/}
}
TY  - JOUR
AU  - Marek Sokołowski
TI  - Bounds on half graph orders in powers of sparse graphs
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11063/
DO  - 10.37236/11063
ID  - 10_37236_11063
ER  - 
%0 Journal Article
%A Marek Sokołowski
%T Bounds on half graph orders in powers of sparse graphs
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11063/
%R 10.37236/11063
%F 10_37236_11063
Marek Sokołowski. Bounds on half graph orders in powers of sparse graphs. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11063

Cité par Sources :