For every δ < 3/2 the ⊆-minimal minor-closed classes with density >δ form a finite explicitly identified set, yielding a 2^poly(n)-time algorithm that computes δ(excl(Z)) or reports ≥3/2 for any finite forbidden-minor set Z.
Kostochka , title =
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
Counting induced k-vertex subgraphs with automorphism group exactly Q is #W[1]-hard for every finite group Q, via clique-scaffold reductions from k-clique.
k-cacti exclude large complete minors and thus have edge density O((log k / sqrt(log log k)) n), tight up to a sqrt(log log k) factor.
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
citing papers explorer
-
Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties
Counting induced k-vertex subgraphs with automorphism group exactly Q is #W[1]-hard for every finite group Q, via clique-scaffold reductions from k-clique.