78 problems

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

Fix $k\geq 2$, and let $\delta$ be small enough. For any $\delta>\delta_0>0$ and sufficiently large $n$, consider every $C_{2k-1}$-free graph $G$ on $n$ vertices satisfying … Korán…

Let $k,r,b$ be integers with $k\geq 2$, $r=2k+b$, and $3\leq b\leq 2k$. Let $T^{**}(r,n)$ be the three-block graph consisting of a complete bipartite block with parts of sizes…

Let $G$ be a graph. A graph is path-perfect if its chromatic number equals the maximum chromatic number of a subgraph spanned by an odd cycle, that is, $\chi(G)=r(G)$. P₅-free path…

A graph $G$ is fork-free if it has no induced subgraph isomorphic to the graph obtained from $K_{1,3}$ by subdividing one edge once. A graph is perfectly divisible if, for each ind…

Let $\lambda>0$ and $p\in\mathbb{N}^+$. For a finite family $\mathcal{F}$ of signed graphs, let $M_{p,\mathcal{F}}(\lambda,N)$ be the maximum of $\operatorname{mult}(-\lambda,G)$ o…

Let $G$ be a finite simple graph. For an induced subgraph $F$ of $G$ and $v\in V(F)$, let $N_F(v)$ be the neighbours of $v$ in $F$. $P_5$ local-density conjecture. There exists…