Open-problem statements, with their sources attached.

WOWII Conjecture 316

Let G be a simple connected graph and let P denote the set of pendant vertices (vertices of degree 1). If |P| ≥ deg_avg(Gᶜ), then G is well totally dominated, where deg_avg(Gᶜ) is the average degree of the complement of G.

Let $f(n)$ be an additive function (so that $f(ab)=f(a)+f(b)$ if $(a,b)=1$) such that $\limsup_{p,k} f(p^k) / \log(p^k) = ∞$ and $f(p^k) = f(p)$ or $f(p^k) = kf(p)$. Is it true that $\limsup_n f(n+1)/f(n) = ∞$?

The known counterexample does not satisfy either of these extra hypotheses, so this variant remains open.

WOWII Conjecture 322

Let G be a simple connected graph on n ≥ 5 vertices. If the maximum over all vertices v of l(v) , the independence number of the neighborhood N(v) of v , is at most 1, then G is well totally dominated.

Here l(v) = α(G[N(v)]) is the independence number of the subgraph induced by the open neighborhood of v.

Prove that there exists some $c>0$ such that $h(n) \sim c \left(\frac{n}{\log n}\right)^{1/2}$ as $n\to \infty$.

WOWII Conjecture 40

For a nontrivial connected graph G the size f(G) of a largest induced forest satisfies f(G) ≥ ceil((p(G) + b(G) + 1)/2) where p(G) is the path cover number and b(G) is the largest induced bipartite subgraph size.

A heuristic of Tao using the Cramér model for the primes suggests this is true with $c=\sqrt{2\pi}$.

WOWII Conjecture 59

For a simple connected graph $G$, the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \lceil \sqrt{\mathrm{residue}(G) \cdot b(G)} \rceil$, where $\mathrm{residue}(G)$ is the Havel-Hakimi residue (the number of zeros remaining after applying the Havel-Hakimi algorithm to the degree sequence until termination) and $b(G)$ is the size of a largest induced bipartite subgraph.

See: Favaron, Mahéo, Saclé (1991) for the residue; DeLaVina's Graffiti.pc for the conjecture.

Are there infinitely many $n$ such that if

is the factorisation into distinct primes then all exponents $k_i$ are distinct?

WOWII Conjecture 61

For a simple connected graph $G$, the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \mathrm{residue}(G) + \lceil \mathrm{diam}(G) / 3 \rceil$, where $\mathrm{residue}(G)$ is the Havel-Hakimi residue and $\mathrm{diam}(G)$ is the diameter of $G$.

See: Favaron, Mahéo, Saclé (1991) for the residue; DeLaVina's Graffiti.pc for the conjecture.

It is likely that there are infinitely many primes $p$ such that $8p^2 - 1$ is also prime.

WOWII Conjecture 65:

For a simple connected graph $G$, the size $f(G)$ of a largest induced forest satisfies $f(G) \ge \operatorname{dist\_min}(A) + \lceil \operatorname{dist\_min}(M) / 3 \rceil$, where $A$ is the set of minimum-degree vertices, $M$ is the set of maximum-degree vertices, and $\operatorname{dist\_min}(S) = \min_{v \notin S} \operatorname{dist}(v, S)$ (see distMin).

Is it true that, for every $r$, there is a $k$ such that if $I_1,\ldots,I_r$ are disjoint intervals of consecutive integers, all of length at least $k$, then

is not a perfect power?

Let $k_1 \geq k_2 \geq 3$. Are there only finitely many $n_2\geq n_1 + k_1$ such that

have the same prime factors?

Erdős thought perhaps if the two products have the same factors then $n_2 > 2(n_1 + k_1)$. It is an open question whether this is true when allowing a finite number of counterexamples.

Erdős was unable to prove that if the two products have the same factors then there must exist a prime between $n_1$ and $n_2$.

Let $p_k$ denote the $k$th prime. For infinitely many $r$ there are at least two integers $p_r < n < p_{r+1}$ all of whose prime factors are $< p_{r + 1} - p_r$.

If $n(n+1)=2^k3^lm$, where $(m,6)=1$, then is it true that $\limsup_{n\to \infty} \frac{2^k3^l}{n\log n}=\infty$?

Is $2^n + 1$ powerful for finitely many $n$?

Is $2^n - 1$ powerful for finitely many $n$?

Is $n! + 1$ powerful for finitely many $n$?