A generalized Turán problem and its applications

DOI10.1145/3188745.3188778zbMath1428.68214arXiv1712.00831OpenAlexW2772897248MaRDI QIDQ5230336

Asaf Shapira, Lior Gishboliner

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph property testinggeneralized Turán problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (14)

Generalized rainbow Turán problems ⋮ The Generalized Rainbow Turán Problem for Cycles ⋮ Generalized planar Turán numbers ⋮ On the maximum number of copies of H in graphs with given size and order ⋮ Generalized Turán problems for even cycles ⋮ Some sharp results on the generalized Turán numbers ⋮ Hierarchy theorems for testing properties in size-oblivious query complexity ⋮ On Turán-good graphs ⋮ Many H-Copies in Graphs with a Forbidden Tree ⋮ The shifting method and generalized Turán number of matchings ⋮ Maximizing five-cycles in \(K_r\)-free graphs ⋮ Counting copies of a fixed subgraph in \(F\)-free graphs ⋮ Generalized Turán problems for disjoint copies of graphs ⋮ \(C_{2k}\)-saturated graphs with no short odd cycles

This page was built for publication: A generalized Turán problem and its applications