29 problems
For every class of finite graphs of bounded degree and every order-invariant cluster first-order logic sentence , there exists a first-order sentence …
Given a graph and an integer , determine whether there exists an edge set with such that every connected component of has diameter at m…
This entry tracks Campbell et al. linear treewidth–Hadwiger conjecture. It narrows the gap between known structural bounds and the conjectured linear dependence on the Hadwiger num…
For each fixed rational , given vectors defining the zonotope , d…
Let be a hereditary class of relational structures. Here, model-checking on is tractable if there is an algorithm that, on input a structure…
Let be a hereditary class of graphs. A class is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from the class using a fixed first-…
Independent-planar-minor MIS conjecture. For every planar and every , MIS is polynomial-time solvable on the class of -free graphs.
Let be a hereditary class of graphs. A class is dependent if it has the model-theoretic non-independence property, and first-order model checking is fixed parameter tr…
Let be a hereditary class of graphs. FO model-checking conjecture. There is an FPT first-order model-checking algorithm for graphs in if and only if…
Let , , and be the parameters of the Map--PDD problem, where is the value of in a phylogenetic tree. Map--PDD conjecture. Map-…
Let be a -colorful minor-closed class, meaning a class of -colorful graphs closed under taking colorful minors. A -colorful rainbow -grid is the…
FP-versus-symmetric subtraction conjecture. is strictly contained in…
Let -CNFSAT denote the satisfiability problem for conjunctive normal form formulas whose clauses have at most literals, and let be the number of variables in the input f…
Let be a minor-closed graph class. For a graph , let denote the minimum number of edge identifications needed to transform into…
Let be an instance of textsc{Induced Matching}, together with a path decomposition of of width . The Strong Exponential Time Hypothesis (SETH) ass…
GI-hardness conjecture. is -hard on -free graphs.
Let be the graph in an instance of M-EPVCB, and let denote its maximum degree. The degree-deficit hardness conjecture. M-EPVCB is W[1]-hard with respect to th…
Let be the edge-weighted bipartite graph in an instance of M-EPVCB, and let and denote the sizes of its two bipartition classes. The minimum-side hardness c…
Let be a hereditary class of structures. A class is monadically NIP if it remains NIP after arbitrary unary predicates are added. Hereditary first-order model-checking…
Induced-subgraph counting hardness conjecture. Then is -hard.
Let be a graph on vertices, and let be a nonnegative integer. Suppose that at least vertices of have degree at least . Combined parameterization conjec…
RPP PSAKS conjecture. RPP has a PSAKS with respect to the parameter .
Let be a graph class, and for every FO formula let be a graph such that is not an induced subgraph of any member of…
Let be a nowhere dense graph class, and let be a graph class FO interpretable in . FO model-checking conjecture. The class ha…
Let be a graph class with bounded expansion, let be a simple first-order graph interpretation scheme, and let be a first-order property to be tested. Th…