110 problems

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…

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…

Let $G$ be a graph of even order, and let $k$ be an integer. A graph is 1-factorable if its edges can be partitioned into 1-factors, equivalently if its chromatic index equals its…

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…

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

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

Let $G$ be a cubic graph that does not contain $K_4$, and let $\tau'_2(G)$ denote its 2-tone edge chromatic number, namely the minimum number of colors needed for a 2-tone edge col…

Yokoi's conjecture. There exists a constant $d$ satisfying the preceding condition: for every $2$-connected graph $G$ of odd order with minimum degree at least $d$, one has…

3-connected minimum-degree conjecture. If

Casselgren, Markström and Pham's conjecture. If $n$ and $d$ are positive integers, and $\varphi$ is a proper edge-precoloring of $K_{n,n}^d$ with at most $nd-1$ precolored edges, t…

Balanced complete-bipartite Cartesian-product conjecture. If any precoloring of at most $k < r$ edges of $G$ can be extended to a proper $\chi'(G)$-edge-coloring of $G$, then any p…

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

Casselgren, Petros and Fufa's conjecture. If every precoloring of at most $k < \chi'(G)$ edges of $G$ can be extended to a proper $\chi'(G)$-edge-coloring, then every precoloring o…

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

Proper open conflict-free chromatic-index conjecture. For every graph $G$ with maximum degree $\Delta$,

Let $G^*$ be an $n$-vertex connected class 1 $\Delta$-regular graph with $\Delta>\frac{n}{3}$. A vertex-splitting replaces a vertex by two adjacent vertices whose neighborhoods par…

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

Let $G$ be a graph with minimum degree $\delta(G)\geq 2$, and let $\chi_{\sum}^{M}(G)$ denote its majority neighbor sum distinguishing index. Majority neighbor sum distinguishing c…