853 problems

Let $G$ be a graph, let $d_v\coloneqq\deg_G(v)$, and let $H$ be an edge-weighted graph, possibly with loops. Define the weighted homomorphism count by … where $H(a,b)$ is the edge…

For every sufficiently large integer $d$ and every sufficiently large $n$, every $n$-vertex $d$-regular sublinear expander contains a Hamiltonian cycle.

There exists an integer $k_0$ such that, for every integer $k\ge k_0$, every graph $G$ of order $n$ satisfying $\alpha(G-S)\ge \alpha(G)$ for every subset $S\subseteq V(G)$ with…

Let $\mathcal{C}_{[4,r]}=\{C_4,C_5,\ldots,C_r\}$. For every integer $r\ge 5$, there exists an integer $n_0(r)$ such that, for every $n\ge n_0(r)$,…

For integers $n,\alpha,k$ satisfying $n\le k\alpha$, $n\ge 2\alpha$, $n\ge \alpha+k$, $\alpha\ge 2$, and $k\ge 3$, define $f(n,\alpha,k)$ to be the minimum of $|E(G)|$ over all $k$…

Let $T$ be a tree of order $n\geq 3$. A set $S\subseteq V(T)$ is a dissociation set if every vertex of the induced subgraph $T[S]$ has degree at most $1$, and it is maximal if it i…

For a graph $H$ and integer $r\ge 2$, say that $H$ is $K_{r+1}$-Turán-good if, for every sufficiently large $n$, the Turán graph $T_r(n)$ maximizes the number of copies of $H$ amon…

Let $G$ be a graph with $m=|E(G)|$ edges, let $\rho(G)$ denote its adjacency spectral radius, and let $W_{2k+1}=K_1\vee C_{2k}$. Determine the sharp upper bound for $\rho(G)$, incl…

Let $K$ be the kite graph obtained from $K_4$ by deleting one edge and then attaching a pendant edge to one of the two vertices of degree $2$ in the resulting graph. For every inte…

For a fixed graph $H$ with $h\ge 3$ edges and no isolated vertices, determine whether every sufficiently large $n$-vertex graph $G$ satisfying the relevant minimum-degree hypothesi…

For every finite family $\mathcal L$ of ordinary forbidden graphs, let $p(\mathcal L)=\min\{\chi(H):H\in\mathcal L\}-1$. The Simonovits Product Conjecture asserts that, for all suf…

For every integer $n\ge 4$, every $2$-connected graph $G$ of order $n$ with minimum degree $\delta(G)\ge \sqrt{3n}$ contains a $2$-connected subgraph of every order…

For a graph $G$, let $\alpha_1(G)$ be the maximum cardinality of an edge set $F\subseteq E(G)$ such that $|F\cap E(T)|\le 1$ for every triangle $T$ of $G$, and let $\tau_1(G)$ be t…

Conjecture 1.1 ([1], Conjecture 1.17). With $\pi_r(\mathcal{F})$ denoting the supremum of the values $\alpha\in[0,1]$ for which there exists an $r$-partite graph $G$ with…

Let $G$ be a graph on $n$ vertices with more than $n^2/4$ edges. Then there exists a triangle $T$ in $G$ and other vertices $y_1,\ldots,y_t$, where $t>(\frac{1}{2}-o(1))n$, such th…

Let $k\geq 3$, and let $h_k(n)$ denote the number of induced copies of $C_{2k+1}$ obtained by evenly blowing up $k$ pairwise non-adjacent vertices in a $C_{2k+1}$ on $n$ vertices.…

Average-degree rainbow path conjecture. If $G$ has average degree at least $d$, then every proper edge-coloring of $G$ contains a rainbow copy of the path on $d$ edges.

For each integer $k\geq2$, consider the Cartesian product $C_{2k}\square P_2$ of the cycle $C_{2k}$ and the path $P_2$. The notation $\operatorname{ex}(n,H)$ denotes the maximum nu…

Let $ex_{\mathcal{P}}(n,2C_4)$ denote the maximum number of edges in an $n$-vertex planar graph containing no two vertex-disjoint copies of the cycle $C_4$. Planar Turán conjecture…

For $\delta>0$, let $\rho(3,7,\delta)$ be the limiting maximum edge density of an $n$-vertex graph with independence number at most $\delta n$ that admits a red/blue coloring with…

For $\delta>0$, let $\rho(3,6,\delta)$ be the limiting maximum edge density of an $n$-vertex graph with independence number at most $\delta n$ that admits a red/blue coloring with…

Let $r(3,q)$ denote the two-color Ramsey number for a triangle and a clique of order $q$. For $q\geq 2$, the Ramsey–Turán density $\rho(3,2q-1)$ is defined using graphs admitting a…

For each integer $k\geq 4$, let $f(k)$ be the auxiliary extremal function from the paper and let $\alpha_{k+2}$ be the coefficient in the asymptotic formula for rainbow saturation,…

Let $K_r$ be the complete graph on $r$ vertices, let $\operatorname{sat}(n,\mathcal{R}(K_r))$ denote the minimum number of edges in an $n$-vertex edge-colored graph containing no r…

Regular Boesch conjecture. If an $(n,kn/2)$ UMRG exists and has girth $g$, then it has maximum girth among all $k$-regular $(n,kn/2)$-graphs and, among the $k$-regular $(n,kn/2)$-g…