32 problems

Let $G$ be a graph, let $X\subseteq V(G)$, and let $c(G-X)$ denote the number of connected components of $G-X$. Define the toughness of $G$ by … with $\tau(G)=\infty$ when $G$ is c…

Let $G$ be a minimally 1-tough graph, meaning that $\tau(G)=1$ and $\tau(G-e)<1$ for every edge $e$ of $G$, where $\tau(G)$ is the toughness of $G$. Kriesell's conjecture. Every mi…

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…

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.

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.

Let $P_4$ be a path on four vertices, let $K_1$ be the one-vertex graph, and let $K_1\cup P_4$ denote their disjoint union. A graph is 1-tough if $|S|\geq\omega(G-S)$ for every ver…

Let $G$ be a connected, non-complete, $d$-regular graph, with adjacency eigenvalues … Let $t(G)$ denote its toughness. The Haemers conjecture. The toughness satisfies … This is a s…

For a graph $G$, write $\delta(G)$ for its minimum degree and $t(G)$ for its toughness. A graph is $2$-solid in the sense used by the paper, and minimally $t(G)$-tough means that i…

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 $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…

For an $r$-regular graph, let its toughness be the minimum of $|S|/k(G-S)$ over cut-sets $S\subseteq V(G)$, where $k(G-S)$ is the number of components of $G-S$. A graph is supertou…

The additive-term conjecture. If

No minimally tough chordal graph conjecture. There exists no minimally $t$-tough chordal graph.

Let $G$ be a finite, simple, undirected graph, and let $t$ be a positive real number. A graph is minimally $t$-tough if its toughness is $t$ and $\tau(G-e)<t$ for every edge…

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…

Let $t_0$ be a finite constant such that every $t_0$-tough graph is hamiltonian, as in Chvátal's toughness conjecture. The 2-toughness conjecture. The value of $t_0$ might be $2$.…

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.

Let $G$ be a graph. It is 2-tough if $|S|\geq 2\,\omega(G-S)$ for every subset $S\subset V(G)$ with $\omega(G-S)>1$, and it is $2K_2$-free if it has no induced subgraph consisting…

Ore-type toughness conjecture. If

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

Let $C_8$ be the eighth subclass in the partition of random Apollonian networks used in the paper, and let $\tau(G)$ denote graph toughness. The $C_8$ toughness conjecture. Every g…

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.…

Let $G$ be a graph, and call it $2$-tough if for every vertex set $S\subseteq V(G)$ whose deletion leaves more than one component, $|S|\geq 2\omega(G\setminus S)$. A Hamiltonian cy…

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