135 problems

Let $P_k$ denote the path on $k$ vertices, let $G$ be a graph, and let $c(G)$ denote its cop number. A graph is $P_k$-free if it contains no induced subgraph isomorphic to $P_k$. S…

Generalized Kriesell conjecture. For every $t>0$, every minimally $t$-tough graph has a vertex of degree $\lceil 2t\rceil$.

Shi and Shan's conjecture. If $G$ is a 1-tough, $2k$-connected, $(K_2\cup kK_1)$-free graph, then $G$ is Hamiltonian.

An oriented graph is a digraph with at most one arc between any two vertices. The transitive tournament $T_k$ is the orientation of the complete graph $K_k$ whose vertices can be l…

Mubayi–Wang conjecture. For all $k,\ell\geq 3$,

Let $G$ be a $K_4$-free graph on $n$ vertices. The Balogh–Clemen–Lidický conjecture. $G$ can be made balanced bipartite by removing at most … edges. This conjecture asks whether th…

Let $G$ be a graph with no induced odd cycle of length at least five. A graph is perfectly divisible if, for every induced subgraph $H$ with at least one edge, its vertex set can b…

Let $G$ be a graph of order $n$. For $k\geq 2$, let $S_{n,k}=K_k\vee\overline{K}_{n-k}$, the graph obtained by joining every vertex of a complete graph of order $k$ to every vertex…

Let $G$ be a graph. It is $H$-free if it contains no induced subgraph isomorphic to $H$, and it is $t$-tough if its toughness satisfies $\tau(G)\ge t$. A graph is Hamiltonian when…

Let $P_k$ be the path on $k$ vertices, and let $\widehat P_k$ be the graph obtained from $P_k$ by adding a new vertex adjacent to every vertex of $P_k$. For a graph $G$, write…

Nevries–Rosenke's conjecture. The leaf powers are exactly the strongly chordal graphs that contain none of $H_1,\ldots,H_7$ as an induced subgraph.

Let $G$ be a finite simple graph, and write $|G|$ for its number of vertices. Two subgraphs are anticomplete if their vertex sets are disjoint and no edge joins the two vertex sets…

For an integer $k\geq 1$, let $\mathcal{C}_k$ be the class of graphs that contain no cycle with exactly $k$ chords. A family of graphs is chi-bounded if there is a function $f$ suc…

A graph is a finite undirected graph, and a minimal separator is a vertex set that minimally separates some pair of vertices. Theta-pyramid-prism-turtle conjecture. There is a poly…

de Freitas–Nikiforov–Patuzzi conjecture. For $k\geq 2$ and a graph $G$ of sufficiently large order $n$, if $G$ has no cycle of length $2k+1$, then

Let $C$ be a finite connected graph whose underlying tree $\tilde C$ is neither a path nor a near-path, and suppose there is a weakly or strongly universal $C$-free graph. Then the…

Let $C$ be a finite or countable graph with no isolated vertices, and decompose it into blocks, its 2-connected components. Let $\tilde C$ be the underlying tree of $C$: its vertic…

Let $C$ be a finite or countable graph with no isolated vertices. Decompose $C$ into its blocks, where each block is a 2-connected component, and let $\tilde C$ be the underlying f…

Generalized spectral closedness conjecture for split graphs. The class $\operatorname{Forb}(\mathcal{F})$ is generalized spectrally closed, but it admits no walk-realizable…

For a graph $G$, let $t(G)$ denote its number of triangles. Let $W_k$ be the wheel formed by joining a new vertex to every vertex of a $k$-cycle, and let $W_{\ge 3}$ denote the fam…

Let $H$ be a graph with chromatic number $\chi(H)\ge 3$, and let $P_k$ denote the path on $k$ vertices. For a family of graphs $\mathcal{F}$, write $\mathrm{ex}(n,\mathcal{F})$ for…

Asymptotic extremal-number conjecture.

Let $C_i$ denote the cycle of length $i$, and let ${\rm ex}_2(n,\{C_3,C_4\})$ be the maximum number of edges in an $n$-vertex graph containing neither a copy of $C_3$ nor a copy of…

Ramsey-type bound conjecture. For every $\chi$-bounded class $\mathcal G$ and every two integers $m,s\ge1$, there exists $C=C(\mathcal G,m,s)\ge1$ such that every $\overline{mK_s}$…

Cocktail-party-free subclass conjecture. For every integer $m\ge1$, the $\overline{mK_2}$-free subclass of every $\chi$-bounded class is linearly $\chi$-bounded.