9 problems

Matching-free polynomial eta-boundedness conjecture. For every integer $t\geq 3$, $M_t$-free graphs are polynomially $\eta$-bounded.

Let $\mathrm{IM}(2,q)$ denote the maximum size of an induced matching in the point-line incidence graph of $\mathbb{F}_q^2$. Prime-field planar induced matching conjecture. There e…

Let $\mathrm{IM}(d,q)$ denote the maximum size of an induced matching in the point-line incidence graph of $\mathbb{F}_q^d$. High-dimensional induced matching conjecture. For every…

For a graph $G$, let $h(G)$ be the smallest size of a subset of $V(G)$ intersecting every maximum independent set, and let $\omega(G)$ denote its clique number. An induced matching…

Let $G$ be a connected well-indumatched graph of girth $11$, and let $C_{11}$ denote the cycle on $11$ vertices. The girth-11 uniqueness conjecture. The cycle $C_{11}$ is the only…

Forbidden-subgraph characterization conjecture. Unless $P=NP$, the dominating induced matching problem is polynomial-time solvable in the class of $M$-free graphs if and only if…

Let $G$ be a connected graph with maximum degree $Deltageq 3$. Let $C5^2$ be the graph obtained from a $5$-cycle by replacing its vertices with independent sets of order $2$, and…

Let $G$ be a graph, let $m(G)$ denote its number of edges, and let $C_5^2$ denote the graph obtained by replacing each vertex of a $5$-cycle with an independent set of order $2$. A…

The induced matching bound. If $G\notin\{C_5^2,K_{3,3}^+\}$ and $\Delta\geq 3$, then