Sparse Balanced Partitions and the Complexity of Subgraph Problems

DOI10.1137/100812653zbMath1229.05125OpenAlexW2054605652MaRDI QIDQ3094934

Noga Alon, Dániel Marx

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/16a250b8c22b6cfab6dde5429f34fdbb1712dc0a

zbMATH Keywords

graph partitionssubgraph problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Beating treewidth for average-case subgraph isomorphism

This page was built for publication: Sparse Balanced Partitions and the Complexity of Subgraph Problems