56 problems

For positive integers $r_1\geq\dots\geq r_\ell$, let $K(r_1,\dots,r_\ell)$ be the multigraph consisting of nested copies of $K_{r_i}$: on vertex set $[r_1]$, overlay a copy of…

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

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…

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

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,

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

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

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…

Let $G$ be a multigraph with maximum degree $\Delta$, 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 e…

Hochbaum–Nishizeki–Shmoys conjecture. There exists a polynomial-time algorithm that finds a proper edge-coloring of every multigraph $G$ using $\max\\{\Delta(G)+1,\Gamma(G)\\}$ col…

Multigraph Overfull Conjecture. If

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

Let $G$ be a graph with maximum degree $4\Delta(G)=\Delta$4 and chromatic index $4\chi'(G)=\Delta+k$4$, where$kgeq 1$. A **maximum$4Delta$4-edge-colorable subgraph** is a$4Delta…

Let $G$ be a connected graph of order $n\geq 4$. Let $\mathcal{M}^{[2]}(H)$ denote the family of multigraphs obtained from a graph $H$ by edge multiplication with edge multipliciti…

Let $G$ be a graph, and let $\mathcal{M}^{[3]}(G)$ be the family of multigraphs obtained from $G$ by edge multiplication with edge multiplicities at most $3$. A multigraph is local…

Let $G$ be an $n$-vertex multigraph with maximum edge-multiplicity $\mu$. Select an orientable embedding of $G$ uniformly at random, and let $F$ denote its number of faces. Multigr…

$S_{12}$-Conjecture. For each cubic graph $G$ admitting a perfect matching, $S_{12}\prec G$.