Open-problem statements, with their sources attached.

WOWII Conjecture 146

For a simple connected graph $G$, $\mathrm{tree}(G) \ge 2 \cdot \mathrm{ecc}(B) / \mathrm{rad}(G^2)$ where $\mathrm{tree}(G)$ is the number of vertices in a largest induced subtree, $\mathrm{ecc}(B)$ is the eccentricity of the boundary vertices of $G$ (eccSet and maxEccentricityVertices), and $\mathrm{rad}(G^2)$ is the radius of the square graph of $G$.

We state the inequality in the form $\mathrm{tree}(G) \cdot \mathrm{rad}(G^2) \ge 2 \cdot \mathrm{ecc}(B)$ to avoid division.

Let $v(n,k)$ count the prime factors of $n+k$ which do not divide $n+i$ for $0\leq i < k$. Is it true that $v_0(n)=\max_{k\geq 0}v(n,k)\to \infty$ as $n\to \infty$?

WOWII Conjecture 160

For a simple connected graph $G$, $L_s(G) \ge \max_v l(v) + \max_v T(v) \cdot c_{C_4}(G)$ where:

• $L_s(G) = \mathrm{SimpleGraph.Ls}\, G$ is the maximum number of leaves over all spanning trees of $G$,
• $\max_v l(v)$ is the maximum local independence number over vertices,
• $\max_v T(v)$ is the maximum number of triangles incident to any vertex,
• $c_{C_4}(G)$ is the number of induced 4-cycles in $G$.

Let $v_l(n) = \max_{k\geq l} v(n,k)$. For every fixed $l$, $v_l(n) \to \infty$ as $n \to \infty$

[ErSe67] Erdős, P. and Selfridge, J. L., Some problems on the prime factors of consecutive integers. Illinois J. Math. (1967), 428--430.

WOWII Conjecture 19

If G is connected then the size b(G) of a largest induced bipartite subgraph satisfies b(G) ≥ FLOOR((∑ ecc(v))/(|V|) + sSup (range (l G))), where ecc(v) denotes eccentricity and l(G) is the independence number of neighbourhoods.

Does $v_1(n) = 1$ have finite solutions?

[ErSe67] Erdős, P. and Selfridge, J. L., Some problems on the prime factors of consecutive integers. Illinois J. Math. (1967), 428--430.

WOWII Conjecture 194

For a simple connected graph G, if α(G) ≤ 1 + l_avg(G), then G has a Hamiltonian path. Here α(G) = G.indepNum is the independence number, and l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number of the neighbourhood. A Hamiltonian path is a walk visiting every vertex exactly once.

Does $V_1(n) = 1$ have finite solutions?

This is a modification of erdos_889.variants.v1_eq_1_finite, which might make it more amenable to attack according to [ErSe67].

[ErSe67] Erdős, P. and Selfridge, J. L., Some problems on the prime factors of consecutive integers. Illinois J. Math. (1967), 428--430.

WOWII Conjecture 198a

For a simple connected graph G, if b(G) ≤ 2 + ecc_avg(G), then G has a Hamiltonian path. Here b(G) is the number of vertices in a largest induced bipartite subgraph, and ecc_avg(G) is the average eccentricity of G. A Hamiltonian path is a walk visiting every vertex exactly once.

If $\omega_k(n)$ counts the number of distinct prime factors of $n$ which are $>k$, then is it true that, for every $k\geq 1$, $\liminf_{n\to \infty}\sum_{0\leq i < k}\omega_k(n+i)\leq k?$

WOWII Conjecture 2

For a simple connected graph G, Ls(G) ≥ 2 · (l(G) - 1) where l(G) is the average independence number of the neighbourhoods of the vertices of G.

Is it true that $\limsup_{n\to \infty}\left(\sum_{0\leq i < k}\omega(n+i)\right) \frac{\log\log n}{\log n}=1,$ where $\omega$ counts the number of distinct prime factors without restriction?

WOWII Conjecture 200

For a simple connected graph G, if tree(G) = ⌈1 + l_avg(G)⌉, then G has a Hamiltonian path. Here tree(G) is the number of vertices of a largest induced tree subgraph, and l_avg(G) = averageIndepNeighbors G is the average over all vertices of the independence number of the neighbourhood. A Hamiltonian path is a walk visiting every vertex exactly once.

Let $2=p_1 < p_2 < \cdots$ be the primes and $k\geq 2$. Is it true that, for all sufficiently large $n$, there must exist an integer in $[n,n+p_1\cdots p_k)$ with $>k$ many prime factors?

WOWII Conjecture 217:

If $G$ is a finite simple connected graph on $n > 1$ vertices and $L_s(G) \le 4 \cdot \chi_{\mathrm{residue}=2}(G) + 2$, then $G$ has a Hamiltonian path. Here $L_s(G)$ is the maximum number of leaves over all spanning trees and $\chi_{\mathrm{residue}=2}(G)$ is the indicator of $\mathrm{residue}(G) = 2$.

This is unknown even for $k=2$ - that is, is it true that in every interval of $6$ (sufficiently large) consecutive integers there must exist one with at least $3$ prime factors?

WOWII Conjecture 291

For a simple connected graph $G$ with $n > 2$, $\gamma_t(G) \le k + \mathrm{frequency}(t_{\min}(v))$ where:

• $\gamma_t(G)$ is the total domination number,
• $k$ is the first step in which a zero appears in the Havel-Hakimi process,
• $\mathrm{frequency}(t_{\min}(v))$ is the number of vertices achieving the minimum triangle count.

Weisenberg has observed that Dickson's conjecture implies the answer is no if we replace $p_1\cdots p_k$ with $p_1\cdots p_k-1$. Indeed, let $L_k$ be the lowest common multiple of all integers at most $p_1\cdots p_k$. By Dickson's conjecture [Wikipedia], there are infinitely many $n'$ such that $\frac{L_k}{m}n'+1$ is prime for all $1\leq m < p_1\cdots p_k$. It follows that, if $n=L_kn'+1$, then all integers in $[n,n+p_1\cdots p_k-1)$ have at most $k$ prime factors.

WOWII Conjecture 314:

For every finite simple connected graph $G$ with $n > 1$ vertices, if $G$ is triangle-free and $\mathrm{path}(G) \le 4$, then $G$ is well totally dominated.

Here $\mathrm{path}(G) = \mathrm{largestInducedPathSize}\, G$ is the size of a largest induced path in $G$, defined locally above. Disambiguation.* Earlier revisions of this file used the SimpleGraph.path invariant, but that is the floor of the average distance, not the size of a largest induced path , a different quantity that makes Conjecture 314 vacuous in many cases.

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))/ \log n = ∞$?

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