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

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

Kang–Kim–Liu conjecture. For every rational number $r\in[1,2]$, there exists a graph $H$ such that

Katona–Xiao conjecture. If $k$ is odd and $(k-1)\mid n$, then the disjoint union of $n/(k-1)$ copies of $T(k-1,m-1)$ gives the maximum number of edges in a graph containing neither…

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…

Let $N_{\alpha}(r)$ be the maximum number of a system of equiangular lines in $\mathbb{R}^r$ with common angle $\arccos\alpha$. The Lemmens–Seidel conjecture concerns the case…

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 $p$ be a prime number, and let $\mathcal C_{\geq p}^{\mathrm{prime}}$ be the family of all cycles of length at least $p$. For integers $n$ and $r$ satisfying $r<p$, let…

Let $k\geq 2$ and let $n$ be sufficiently large. Let $G$ be an $n$-vertex graph containing no cycle $C_{3\ell+1}$ for any integer $\ell\geq k$. For $r\geq 2$, write $N_r(G)$ for th…

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…

Asymptotic extremal-number conjecture.

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.

Let $G$ be a graph, and let $P_6$, $G_4$, and $G_5$ be the graphs described in Figure 5 of the source. Puech's conjecture. If $G$ does not contain $P_6$, $G_4$, or $G_5$ as induced…

A graph is $P_5$-free if it has no induced subgraph isomorphic to the path $P_5$. Faudree–Favaron–Li conjecture. Any $P_5$-free graph is irredundance perfect. Puech proved this con…

Let $G$ be a graph, and let $P_6$, $G_1$, and $G_2$ be the graphs described in Figure 5 of the source. Favaron's conjecture. If $G$ does not contain $P_6$, $G_1$, or $G_2$ as induc…

Generalized Hamilton-connectedness conjecture. Every $r$-connected ${K_{1,r+1},K_{1,r+1}+e}$-free split graph of order at least $2r+7$ is Hamilton-connected.

Ryjáček et al.'s conjecture. Every $4$-connected ${K_{1,4},K_{1,4}+e}$-free graph with minimum degree at least $6$ is Hamiltonian.

Let $q$ be a prime power and let $n=q^2+q+1$. For an $n$-vertex $C_4$-free graph $G$, write $\tau(G)$ for its number of spanning trees, and let $\mathrm{st}(n,C_4)$ denote the maxi…

Let $\mathrm{er}_{s}(\{\overline{K}_3,C_5\})$ denote the minimum asymptotic density of $s$-cliques among graphs avoiding both $\overline{K}_3$ and $C_5$. Theorem's extension conjec…

Let $P_k$ denote the path on $k$ vertices, let $\operatorname{claw}=K_{1,3}$, and let $c(G)$ denote the cop number of a graph $G$. A graph is $(P_k,\operatorname{claw})$-free if it…

Let $n\geq k\geq 4$. For a graph $F$, let $\widehat{F}$ denote the graph obtained by adding a vertex adjacent to every vertex of $F$, and let $\operatorname{ex}(n,H,F)$ be the maxi…