41 problems

Let $G_{n,\ell}:=K_{\underbrace{n,n,\ldots,n}_{\ell}}$ be the complete multipartite graph with $\ell$ parts, each of size $n$, and let $Z_q(G)$ denote the $q$-analogue of the zero…

Let $G$ be a $k$-chromatic graph with at most $mk$ vertices, and let $K_{m*k}$ denote the complete $k$-partite graph with $m$ vertices in each part. Noel's conjecture. … The conjec…

A complete $k$-partite graph is a graph whose vertices are partitioned into $k$ independent parts, with every pair of vertices in distinct parts adjacent. He et al.'s conjecture. A…

For a graph $G$, let $\chi(G)$ be its chromatic number, and let $\chi_\ell(G)$ be its list chromatic number. A graph is chromatic-choosable when $\chi_\ell(G)=\chi(G)$. Ohba's conj…

Let $K_{n_1,n_2,\ldots,n_k}$ be a complete multipartite graph with $k\geq 3$. Let $-K_{n_1,n_2,\ldots,n_k}$ denote the signature in which every edge is negative, and write $l(-G)$…

Let $\mathcal{M}$ be the family of complete multipartite graphs, and let $I_H(x)$ denote the inducibility profile of a graph $H$. Unbounded-local-maxima conjecture. For every $k>0$…

The conjectured profile of $K_{2,2,1}$. The function is conjectured to satisfy

Let $\mathcal{G}_r(n)$ be the class of $r$-partite graphs with parts of size $n$. An independent transversal with exactly $s$ vertices in each part is denoted by $IT(s)$. Odd-parti…

Let $K_n^4$ denote the complete balanced $4$-partite graph with $n$ vertices, and let $\operatorname{cr}(G)$ and $\overline{\operatorname{cr}}(G)$ denote respectively its ordinary…

Let $k\ge 2$ and let $G$ be a $k$-partite graph with parts $V_1,\ldots,V_k$ of the same size $n$. Define the partite minimum degree of $G$ to be the largest integer $d$ such that e…

Multipartite Dirac conjecture. The Hamiltonicity threshold should converge to $\frac{1}{2}$ as $r\rightarrow\infty$:

Connected transversal conjecture. The lower bound in Theorem is tight. In particular, for any $r\geq 4$, every $r$-partite graph with $r$-partite density at least…

Let $r\geq t\geq 3$ and $k\geq 2$, and let $K_{t}$ denote the complete graph on $t$ vertices. For positive integers $n_1,\ldots,n_r$, write $K_{n_1,\ldots,n_r}$ for the complete…

Let $k,p,t\geq 2$ be integers. For a complete $p$-partite graph $H=K_p(a_1,\dots,a_p)$ with $1\leq a_1\leq\cdots\leq a_{p-1}\leq t$ and $a_p\leq\delta n$, let $B_{k,n}$ be the book…

Let $B_{r,k}=K_r\vee I_k$ be the generalized book formed by joining every vertex of a clique $K_r$ to every vertex of an independent set $I_k$. Let $G$ be a graph with $m$ edges, a…

Let $k\geq r\geq 2$ and $\gamma>0$. Let $G$ be a $k$-partite graph on $n$ vertices with parts $V_1,\ldots,V_k$ such that $|V_i|\leq n/r$ for every $i$. For each $i\in [k]$, write…

Let $\bm{k}=(k_1,\hspace{0.9pt}.\hspace{0.3pt}.\hspace{0.3pt}.\hspace{1.5pt},k_s)$ be a non-increasing sequence of natural numbers, and let a graph be $\bm{k}$-extremal if it attai…

The conjecture on $f(k)$. For every $k\ge 2$,

Let $r\ge 3$ and let $n_{1}\ge n_{2}\ge \cdots\ge n_{r}\ge 1$. Let $K_{n_{1},n_{2},\ldots,n_{r}}$ be the complete $r$-partite graph with parts of these sizes, let $G$ be a subgraph…

Let $H$ be a multipartite $k$-hypertournament, where $k\ge 2$. A vertex is a transmitter if it has no incoming arc with any vertex from a different partite set, and a 4-king is a v…

Structural conjecture. There exists $\alpha_0>0$ such that, for every $0\leq\alpha\leq\alpha_0$ and every $K_{r+1}$-free graph $G$ on $n$ vertices, there is an unbalanced blow-up…

The general multipartite Turán conjecture. The Turán number of the disjoint union $kK_t$ in the complete $r$-partite graph is

Let $K_{n,n,n}$ be the complete tripartite graph with three parts of size $n$, and let $P_m$ denote the path on $m$ vertices. For graphs $G_0,G_1,G_2$, write $G_0\mapsto(G_1,G_2)$…

Gyárfás–Rusza–Sárközy–Szemerédi conjecture. For every positive integer $n$,

Matching sequencibility conjecture. For any integers $n\geq 2$ and $s\geq 2$,