110 problems

Two-cliques edge-coloring conjecture. The signed edge-chromatic number satisfies

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…

Erdős–Nešetřil conjecture. The strong chromatic index of $G$ satisfies

Let $G$ be a finite, undirected, loopless simple graph, let $|G|$ denote its number of vertices, let $\Delta=\Delta(G)$ be its maximum degree, and let $\overline{d}(G)$ be its aver…

General Cartesian-product conjecture. Every precoloring of at most $k+l+1$ edges of $G \square H$ is extendable to a proper $(\chi'(G)+\chi'(H))$-edge-coloring of $G \square H$.

Vizing's conjecture. Every $k$-edge-coloring of a graph $G$ is equivalent to a $\Delta(G)$-edge-coloring of $G$ if there is any.

Let $G$ be a subcubic graph. The Dvořák–Mohar–Šámal conjecture. … The star chromatic index is the minimum number of colors in a star edge-coloring, in which every bichromatic subgr…

Jakobsen's bounded-order conjecture. If

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…

Planar D-chromatic index conjecture. For every such graph,

Let $K_n$ be the complete graph on $n$ vertices, let $\sigma$ be a signature on $K_n$, and let $\chi ' (K_n, \sigma)$ denote its signed chromatic index. Chromatic-index conjecture.…

Overfull Conjecture. Let $G$ be a graph of Class $2$ with

Burris–Schelp conjecture.

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 graph, let $k$ be an integer, and write $G\square K_2$ for the cartesian product of $G$ and the complete graph on two vertices. Write $\chi'(G)$ for the edge-chromatic…

Let $Q_d$ be the $d$-dimensional hypercube, and let $\varphi$ be a partial $d$-edge coloring of $Q_d$. A color class is the set of edges receiving one fixed color, and an induced ma…

Weak oddness versus resistance conjecture. One has

Let $G$ be a simple graph. Denote its group edge chromatic number by $\chi'_g(G)$ and its group list edge chromatic number by $\chi'_{gl}(G)$. Equality conjecture. For every simple…

Let $G$ be an admissible graph, and let ${\mathrm Maj'}(G)$ denote the minimum number of colors in a strong majority edge-coloring of $G$. Upper-bound conjecture. If $G$ is an admi…

Let $G$ be an $r$-regular graph with maximum degree $\Delta$ and edge-chromatic number $\chi'(G)=\Delta+1$. A maximum $\Delta$-colorable subgraph is a subgraph with as many edges a…

Let $G$ be a graph with maximum degree $\Delta$ and edge-chromatic number $\chi'(G)=\Delta+k$, and let $p,q$ be positive integers satisfying … with $p,q\leq\Delta$. A graph is clas…

MED decomposition conjecture. Every 2-connected graph with maximum degree 3 has a MED decomposition.

List-chromatic-index criticality conjecture. Every $\chi'_\ell$-critical graph is $\chi'$-critical.

Zhang's conjecture. If $G\neq C_5$ and $G\neq K_2$, where $C_5$ is the cycle of size $5$, then the avd-chromatic number of $G$ is at most

Let $G$ be a $2$-connected cubic graph with no Petersen minor. A proper three-edge-coloring assigns one of three colors to each edge so that edges incident with the same vertex rec…