71 problems

Let $G$ be a general multigraph, let $\chi'(G)$ denote its chromatic index, let $\Delta(G)$ denote its maximum degree, and let $\mathcal{W}(G)$ denote its density parameter. Goldbe…

Let $G$ be a finite undirected multigraph, allowing parallel edges and loops, and call $G$ bridgeless if it has no bridge. A cycle double cover of $G$ is a finite multiset of cycle…

Let $G$ be a finite, undirected, loopless multigraph. Write $\Delta=\Delta(G)$ for its maximum degree, $\chi'(G)$ for its chromatic index, and $\overline{d}(G)$ for its average deg…

Local Irregularity Conjecture for 2-multigraphs. For every connected graph $G$ which is not isomorphic to $K_2$,

Let $G$ be a loopless multigraph, with maximum degree $\Delta(G)$, and define … A $\max\{\Delta(G)+1,\Gamma(G)\}$-edge-coloring assigns at most that many colors to the edges of $G$…

Jakobsen's bounded-order conjecture. If

Let $G$ be a multigraph, and let $E_1,\ldots,E_n$ be color classes of a proper edge-coloring of $G$. A full rainbow matching is a matching containing exactly one edge from each col…

Day–Falgas-Ravry–Treglown conjecture. For all integers $a,r,s,d$ with $a,r\geq 1$, $d\in[0,a-1]$, $s\geq(r-1)(d+1)+2$, and all sufficiently large $n$,

Goldberg's density conjecture. For any graph $G$, if $\Gamma(G)\le\Delta(G)-1$, then

Let $L_1,R_1,L_2,R_2$ be vertex sets of sizes $n_1,k_1,n_2,k_2$, respectively, satisfying … Let $(L_1,R_1,E_1,u_1,v_1)$ and $(L_2,R_2,E_2,u_2,v_2)$ be biregular bipartite labeled m…

Let $M$ be a binary $n\times k$ matrix with non-negative integer entries, row sums $k$, and column sums $n$. Let $M\otimes M^T$ be the matrix associated with the corresponding tens…

Let $\Gamma=(V,E)$ be a $(d,\ell)$-tight multigraph, with $\ell<\frac{4d+2}{3}$. Let $K_2^{2k-\ell}$ denote the graph with two vertices and $2k-\ell$ parallel edges, and let a $d$-…

Brown–Erdős–Simonovits conjecture. For any $q$, every density $alpha\in[0,q)$ is a jump for $q$-multigraphs. Brown, Erdős, and Simonovits proved that every density $alpha\in[0,2)$…

Let $s\in\mathbb{Z}_{\geq 4}$, and let $G=G^{(a)}$ be any graph pattern in the statement, with ambient edge multiplicity $a=2$. Multiplicative conjecture. If … then … For all…

Let $s\in\mathbb{Z}_{\geq 4}$, and let $G=G^{(a)}$ be any graph pattern in the statement, with ambient edge multiplicity $a=1$. Additive conjecture. For every $k\geq 4$, if … then…

Let $s\geq 2$ and let $q$ be a non-negative integer. An $(s,q)$-graph is a multigraph satisfying the paper's $(s,q)$-constraint, and $P(G)$ denotes the product of its edge multipli…

Let $s\in\mathbb{Z}_{\geq 2}$ and let $q$ be an integer with $0\leq q<\binom{s}{2}$. A generalized Turán pattern is a pattern $T=\mathrm{T}[\mathbf{r};a]$ whose blow-ups are…

Let $\mathrm{T}[(r);a]$ be the generalized Turán pattern with parameter $r$ and ambient edge multiplicity $a$, and let $\Sigma_s(\mathrm{T}[(r);a])$ denote its associated threshold…

Day, Falgas–Ravry and Treglown's conjecture. For all $n$ sufficiently large,

Let $G$ be an $r$-graph. Replacing every edge of $G$ by two parallel edges gives its double. The doubled-edge conjecture. For every $r$-graph, it is sufficient to replace every edg…

Strengthened Alon–Wei conjecture. There exists an absolute constant $c>0$ such that for every $n,d\geq 2$, there is a spanning subgraph $H$ of $G$ satisfying

Multigraph non-3-colorability conjecture. There exists an undirected countable multigraph that is not majority 3-colorable.

(2,2)-Conjecture. The graph $G$ can be decomposed into two subgraphs $G_1$ and $G_2$ such that there exist locally irregular multigraphs $M_1$ and $M_2$ satisfying

KPTU's conjecture. Every separated single-crossing, but not necessarily locally star-like, drawing on $n$ vertices has

Let $H$ be a multigraph. Its chromatic index $\chi'(H)$ is the least number of colors in a proper edge-coloring, and its list chromatic index $\chi'_{\ell}(H)$ is the least integer…