884 problems

For a finite tree $T$ with vertex degrees $d(v)$, define its Euler Sombor index by $EUS(T)=\sum_{uv\in E(T)}\sqrt{d(u)^2+d(v)^2+d(u)d(v)}$. For trees with a prescribed diameter $d$…

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 $\varepsilon>0$, there exist constants $c_{\varepsilon}>0$ and $n_{0}(\varepsilon)$ such that, for every $n\geq n_{0}(\varepsilon)$ and every $n$-vertex graph $G$ that is…

For every prime power $q>7$ and every $a_0\in\mathbb{F}_q$, there exists a circular permutation $(a_1,\ldots,a_{q-1})$ of $\mathbb{F}_q^{\times}$ such that, with $a_q=a_1$, each el…

For every edge-color-critical graph $F$ with $\chi(F)=r+1$, and every positive integer $n$, let $\mathcal{G}_{n,r}(F)$ be the family of all $n$-vertex, $F$-free graphs that are not…

For every $\varepsilon>0$, there exists a constant $c_{\varepsilon}>0$ such that, for every sufficiently large $n$, every integer $d\leq (1-\varepsilon)n/2$, and every $d$-regular…

Let $G$ be an $(n,d,\lambda)$-graph, meaning a $d$-regular graph on $n$ vertices whose nontrivial adjacency eigenvalues have absolute value at most $\lambda$. For every $\delta>0$,…

For every odd integer $n\ge 7$, does every $n$-vertex graph $G$ satisfying $\delta(G)\ge \lceil n/2\rceil$ contain a spanning subgraph isomorphic to the graph obtained from the squ…

For every integer $n\ge 1$, determine the exact value of…

For each integer $n\ge 3$, consider the unbiased Maker–Breaker game on the edge set of $K_n$: in each round Maker claims one previously unclaimed edge, and then Breaker claims $q$…

For every integer $n$ and every triangle-free graph $G$ on $n$ vertices, if $\delta(G)>n/3$, then $\chi(G)\le 4$.

For every pair of integers $n,k$ with $2\le k\le n/2$, and every $n$-vertex graph $G$ satisfying $e(G)\ge k(n-k)$, define $\mathcal{C}(G)$ to be the set of cycle lengths occurring…

Let $k\ge 2$, $k\le \delta\le 2k-1$, and set $h=\delta-k$. For all sufficiently large $n$, among the graphs $G\in\mathcal{L}_{\mathcal{H}}^{2}(n,k,\delta)$, the graph maximizing th…

For every integer $k\ge 1$ and every $\varepsilon>0$, there exists an integer $r_0=r_0(k,\varepsilon)$ such that every $r$-regular graph $G$ on $n$ vertices, with $r\ge r_0$, conta…

There exists a universal constant $C>0$ such that, for every finite graph $H$, the fractional expectation threshold for containing $H$ satisfies…

For every integer $k\ge 2$, every oriented graph $D$ with chromatic number $\chi(D)\ge 2k-2$ contains every oriented tree $T$ on $k$ vertices as an oriented subgraph. Equivalently,…

For every integer $t\ge 1$, every oriented tree $T$ with $t$ edges, and every loopless digraph $D$ on $n$ vertices with no repeated arcs, if opposite arcs are permitted, $D$ is Eul…

For every integer $k\ge 2$, every oriented graph $G$ with minimum semidegree $\delta^0(G):=\min\{\delta^+(G),\delta^-(G)\}>k/2$ contains, as a subgraph, every orientation of the pa…

For all positive integers $n$ and $k$, every digraph $D$ on $n$ vertices with more than $(k-1)n$ arcs contains every antidirected tree $T$ with $k$ arcs as a subdigraph. Here, an a…

For an integer $r\ge 2$ and a real number $0<\delta<1/r$, let $b_n(r,\delta)$ be the largest integer $b$ such that every graph $G$ on $n$ vertices satisfying…

For every fixed integer $k\ge 2$, there exists a constant $C_k$ such that every graph $G$ on $n$ vertices with at least $C_k n$ edges contains pairwise edge-disjoint cycles…

For an integer $p\ge 3$, let $\operatorname{ex}(n,K_r)$ denote the maximum number of edges in an $n$-vertex $K_r$-free graph. For integers $n$ and $m$, define $f_{p+1}(n,m)$ to be…

For every integer $r\ge 3$ and every finite graph $F$ satisfying $\chi(F)=r$ and $\operatorname{tw}(F)\ge r$, there exist constants $c_F>0$ and $n_0(F)$ such that, for every intege…

For all integers $l>k\ge 2$, let $\mathscr{C}_{2k}=\{C_3,C_4,\ldots,C_{2k}\}$. Then … where $\operatorname{ex}(n,H,\mathcal{F})$ is the maximum number of copies of $H$ in an $n$-ve…

For every connected graph $G$ with $n$ vertices, let $\mathcal{P}(G)$ be the set of its simple subpaths, including the one-vertex paths, and define…