195 problems

Polynomial-time branchwidth conjecture. Branchwidth can be computed in polynomial time on $H$-minor-free graphs.

Let $\mathcal F$ be the class of graphs $G$ such that no component of $G$ contains every finite graph as a minor. A graph $U$ is $<$-universal for a class if every graph in the cla…

Let ${\mathcal C}_0$ be a proper minor-closed class of countable graphs. For a minor-closed graph family ${\mathcal C}$, let $\Delta({\mathcal C})$ be the smallest cardinal $k$ suc…

Forbidden-minor characterization conjecture. The following are equivalent:

Let $G$ be a graph with chromatic number $[?]{}$ and let $S\subseteq V(G)$ be colorful if every proper $\chi(G)$-coloring of $G$ assigns all $\chi(G)$ colors to vertices in $S$. An…

Polynomial weak colouring-number conjecture. There exists a function $f$ such that for every $K^*_{s,t}$-minor-free graph $G$ and every $r\geqslant1$,

The preceding theorem gives a bound on rooted $K_{3,3}$ minors; denote this bound by the quantity appearing in Theorem. Tightness conjecture. The bound in Theorem is tight. This co…

Let $G$ be a graph of tree-depth $k$, meaning that $k$ is the least number of labels in a vertex ranking of $G$ such that every path joining two vertices with the same label contai…

Let $G$ be a graph and let $I_G$ be its cut ideal. A graph is $K_5$-minor-free when it has no minor isomorphic to $K_5$. Quartic generation conjecture. … This extends the proposed…

Let $G$ be a graph, let $I_G$ be its cut ideal, and let $\mu(I_G)$ denote the maximal degree of a binomial in a minimal generating set of $I_G$. A graph $H$ is a minor of $G$ if it…

Let $\mathsf G$ be a graph and let $e,f$ be edges of $\mathsf G$. Write $\Delta Z(\mathbf I\mathsf G)\{e,f\}$ for the Rayleigh difference of the independence-set partition function…

Let $G=(V,E)$ be a graph with no stable set of size $3$, and let a prevertex be a connected subgraph contracted to one vertex in a minor. Seymour's strengthening. The graph $G$ has…

Edge-deletion monotonicity conjecture. If $H$ is obtained from $G$ by deleting an edge, then

Let $G$ be a finite graph and let $t\in\mathbb{N}$. A minor of $G$ is a graph obtainable from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions; write…

Linear Erdős–Pósa conjecture. At least one of the following holds:

Coarse Erdős–Pósa conjecture. There exist functions

Let $\mathcal{F}$ be a class of graphs, and let $\equiv_{\mathcal{F}}$ denote the relation on graphs defined by equality of homomorphism counts from every graph in $\mathcal{F}$. A…

Let $\mathcal{F}$ be a class of graphs. It is homomorphism distinguishing closed if it is maximal among the classes defining its homomorphism indistinguishability relation. A graph…

For a graph class $\mathcal{G}$, let $\operatorname{obs}(\mathcal{G})$ denote its minor obstruction set. For a class property $\mathbb{C}$, let $\operatorname{cobs}(\mathbb{C})$ be…

For a graph class $\mathcal{G}$, let $\operatorname{obs}(\mathcal{G})$ denote its minor obstruction set. For a class property $\mathbb{C}$, let $\operatorname{cobs}(\mathbb{C})$ be…

Bounded-cycle-space fat minor conjecture. For every graph $X$ there exists a function $f:\mathbb{N}^2\to\mathbb{N}^2$ such that, for every graph $G$ whose cycle space is generated…

Fat minor conjecture. For every graph $X$ there exists a function $f:\mathbb{N}\to\mathbb{N}^2$ such that, for every graph $G$ and $K\in\mathbb{N}$, if $G$ does not contain $X$ as…

Let $G$ be a $5$-connected non-planar graph with at least seven vertices. Kawarabayashi–Maharry conjecture. The graph $G$ contains both a $K_{3,4}$ minor and a $K_6^-$ minor. The s…

Let $k$ be a positive integer, and consider the class of $k$-connected bipartite graphs with the bipartite minor relation. Bipartite-minor non-well-quasi-order conjecture. There ex…

For a graph $G$, its Hadwiger number is the largest integer $t$ such that $G$ contains the complete graph $K_t$ as a minor. Two graphs are homomorphism indistinguishable over a gra…