62 problems

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

Let $r=r(n)$ be an integer-valued function such that $r\mid 2n$, and let $G=K_{r\times 2n/r}$ be the balanced complete $r$-partite graph on $2n$ vertices. If $M$ is a perfect match…

Let $f(G)$ denote the oriented diameter parameter for a graph $G$, and let ${\sf K}(2,p,q)$ be the complete tripartite graph with part sizes $2$, $p$, and $q$, where $p$ and $q$ ar…

Let $G$ be a complete $r$-partite graph, and let $mu_{\operatorname{int}}(G)$ denote its interval coloring impropriety. Impropriety conjecture for complete multipartite graphs. … T…

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

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…

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 $G$ be a complete $k$-partite graph, and let $e$ be an edge of $G$ such that $G\backslash\{e\}$ remains connected. The distance energy of a graph is the sum of the absolute val…

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 $\mathcal{G}_r(n)$ be the class of $r$-partite graphs whose parts all have size $n$. Let $\Delta_r(n)$ be the largest integer $C$ such that every graph in $\mathcal{G}_r(n)$ wi…

Let $G$ be a tripartite graph with parts of size $n$, and let $\delta(G)$ denote its minimum degree. A complete tripartite graph with $s$ vertices in each part is denoted by…

Let $r$, $k$, $t$, and $n$ be integers, with $t\ge 2$ and $r<k\le 2r$. Let $\operatorname{ex}_k(n,K_{r+1}(t))$ denote the maximum number of edges in a $k$-partite graph on $n$ vert…

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_n^3$ denote the complete balanced tripartite graph with $n$ vertices, and let $\operatorname{cr}(G)$ and $\overline{\operatorname{cr}}(G)$ denote respectively the ordinary a…

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…

For a graph $H$, say that $H$ is multibounding if, for every integer $d\geq 1$, there is a polynomial $f(t)$ such that, for all $t\geq 1$, every $H$-free graph $G$ that does not co…

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 $r$ and $k$ be positive integers, let $B_{r,k}$ denote the join of an $r$-clique with an independent set of size $k$, and let $G$ be a $B_{r,k}$-free graph with sufficiently la…

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…