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.
Title resolution pending
5 Pith papers cite this work, alongside 587 external citations. Polarity classification is still indexing.
5
Pith papers citing it
587
external citations · OpenAlex
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
unclear 1representative citing papers
GNTC satisfiability is 2-EXPTIME-complete and GNTC model checking is P^{NP[O(log^2 n)]}-complete, settling open bounds for UNTC and UNFO^reg.
Verifies stronger coarse balanced separator conjecture for all r in K_{t,t}-induced-minor-free graphs of bounded clique number via a polynomial-size hitting set Z for large balls on any Y.
For trees the lion number satisfies pw(T) ≤ L(T) ≤ pw(T)+1; for connected graphs L(G) ≤ pw(G)+1 and the monotone lion number obeys pw(G) ≤ L^m(G) ≤ 2pw(G)+2, with monotonicity holding for isometric subgraphs but not arbitrary ones.
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.
citing papers explorer
-
Obstructions for Minor-Closed Classes of limiting Densities Below 3/2
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.
-
Guarded Negation Transitive Closure Logic
GNTC satisfiability is 2-EXPTIME-complete and GNTC model checking is P^{NP[O(log^2 n)]}-complete, settling open bounds for UNTC and UNFO^reg.
-
Coarse Balanced Separators in Biclique-Induced-Minor-Free Graphs
Verifies stronger coarse balanced separator conjecture for all r in K_{t,t}-induced-minor-free graphs of bounded clique number via a polynomial-size hitting set Z for large balls on any Y.
-
Lions and Contamination: Trees and General Graphs
For trees the lion number satisfies pw(T) ≤ L(T) ≤ pw(T)+1; for connected graphs L(G) ≤ pw(G)+1 and the monotone lion number obeys pw(G) ≤ L^m(G) ≤ 2pw(G)+2, with monotonicity holding for isometric subgraphs but not arbitrary ones.
-
An Overview of Universal Obstructions for Graph Parameters
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.