Bounds on half graph orders in powers of sparse graphs

DOI10.37236/11063OpenAlexW4362699105MaRDI QIDQ2699651

Marek Sokołowski

Publication date: 19 April 2023

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

cagessemi-ladders in planar graphsupper bound for planar graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics of partially ordered sets (06A07) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Colouring graphs with bounded generalized colouring number
• Characterising bounded expansion by neighbourhood complexity
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• Grad and classes with bounded expansion. I: Decompositions
• On nowhere dense graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Tree-depth, subgraph coloring and homomorphism bounds
• Domination Problems in Nowhere-Dense Classes
• Linear time low tree-width partitions and algorithmic consequences
• Intersection Theorems for Systems of Sets
• Two lower bounds for $p$-centered colorings
• The Grad of a Graph and Classes with Bounded Expansion
• Applications of a Planar Separator Theorem
• Stable graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Coloring and Covering Nowhere Dense Graphs
• Kernelization and Sparseness: the case of Dominating Set
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
• Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
• Deciding First-Order Properties of Nowhere Dense Graphs
• First order properties on nowhere dense structures
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On the number of types in sparse graphs
• Linear rankwidth meets stability
• Improved bounds for centered colorings
• Testing first-order properties for subclasses of sparse graphs
• Regularity lemmas for stable graphs
• Parameterized Algorithms
• An inequality for the chromatic number of a graph
• k-Degenerate Graphs
• On the generalised colouring numbers of graphs that exclude a fixed minor

This page was built for publication: Bounds on half graph orders in powers of sparse graphs