17 problems

Let $t$ be a real number, and let $G$ be a graph. A graph is minimally $t$-tough when $\tau(G)=t$ and $\tau(G-e)<t$ for every edge $e\in E(G)$, where $\tau(G)$ denotes its toughnes…

Let $t>0$. A graph is non-regular if its vertex degrees are not all equal, and a minimally $t$-tough graph is a $t$-tough graph whose toughness decreases after deleting any edge. Z…

Let $t>0$, and let a minimally $t$-tough graph be a $t$-tough graph whose toughness decreases after deleting any edge. Katona–Varga's generalized conjecture. Every minimally $t$-to…

Let $k\ge 4$ be an integer. A graph is $t$-tough if its toughness satisfies $\tau(G)\ge t$, a graph is $r$-connected if deleting fewer than $r$ vertices leaves it connected, and…

Let $k$ be an integer with $k\ge 4$, and let $G$ be a graph. Here $P_n$ denotes the path on $n$ vertices, $P_2\cup kP_1$ is the disjoint union of a two-vertex path and $k$ isolated…

Let $G$ be a graph of order at least three, and write $\omega(G\setminus S)$ for the number of components of $G\setminus S$. A connected $\\{2,4\\}$-factor is a connected spanning…

Let a $t$-tough graph $G$ satisfy $\omega(G\setminus S)\leq\max\\{1,\frac{1}{t}|S|\\}$ for every $S\subseteq V(G)$. A spanning closed $1$-trail is a spanning closed trail meeting e…

Shi–Shan conjecture. Let $k\geq 4$ be an integer and let $G$ be a $1$-tough and $2k$-connected $(P_2\cup kP_1)$-free graph. Then $G$ is hamiltonian.

Ore-type toughness conjecture. If

Let $G$ be a connected $d$-regular graph, let $t(G)$ denote its toughness, and let $\lambda$ be the second largest absolute eigenvalue of the adjacency matrix of $G$. Brouwer's tou…

The toughness conjecture for Kneser graphs. If $k\geq 5$ and $n\geq 2k+1$, then

Kaiser et al.'s prism-toughness conjecture. There exists a constant $t_1$ such that the prism over any $t_1$-tough graph is hamiltonian.

Let $G$ be a graph. A connected $\{2,4\}$-factor is a connected spanning subgraph of $G$ in which every vertex has degree either $2$ or $4$. Connected $\{2,4\}$-factor conjecture.…

Min-$t$-Tough complexity conjecture. ${\scshape Min-}t$-Tough is DP-complete for any positive rational number $t$.

The $\frac{5}{4}$-tough spanning 2-trail conjecture. Any $\frac{5}{4}$-tough $2K_2$-free graph with at least three vertices has a spanning 2-trail.

Mou and Pasechnik's conjecture. Every $2$-tough $2K_2$-free graph with at least three vertices is hamiltonian.

Let $G$ be a graph of order $n$, let $\tau(G)$ denote its toughness, let $\rho(G)$ denote the independence number, and let $\sigma_3(G)$ be its smallest union degree of order $3$:…