19 problems

Joos's conjecture. The bound holds for every graph $G$ with $\Delta(G)\geq 3$, except for certain graphs listed by Joos.

Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel's conjecture. For every fixed $r$ and formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS can be solved in polynomial time…

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…

Exact extremal conjecture. The inequality $|M_G|\le I(n)$ holds, and equality holds if and only if $G=F_n$.

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_{m,n}$ be a stacked-book graph with $n$ odd. The maximum induced matching number conjecture asserts … The preceding theorem establishes these quantities as lower bounds, and…

Let an $(r,t)$-Ruzsa–Szemerédi graph be a graph whose edges can be partitioned into $t$ pairwise disjoint induced matchings, each of size $r$. Here $n$ is the number of vertices, a…

Polynomial-time DIM conjecture. For every fixed $i,j,k$, DIM is solvable in polynomial time for $S_{i,j,k}$-free graphs; in particular, this includes $P_k$-free graphs for…

Her-Loz-Ries-Zam-de W conjecture. For every fixed $i,j,k$, DIM is solvable in polynomial time for $S_{i,j,k}$-free graphs.

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…

Let $G$ be a graph of maximum degree $\Delta$, and let $\nu_s(G)$ and $\nu_s^*(G)$ denote, respectively, the maximum size of an induced matching in $G$ and the optimum value of its…

Marinescu-Ghemaci's conjecture. The $MIM$ numbers of grids can be found in polynomial time.

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

Let a graph on $N$ vertices have positive density, meaning that it contains a constant-order fraction of all possible edges. Meshulam's conjecture. For every fixed $\delta>0$, such…

Let an $(r,t)$-RS graph be a graph whose edges are the disjoint union of $t$ induced matchings, each of size $r$. A graph has positive density when it has a constant-order fraction…