180 problems

Petruševski–Škrekovski conjecture. If $\chi'_o(G)=4$, then there is an edge whose removal makes $G$ odd $3$-edge-colorable.

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

Let $G$ be a graph of even order $n$, and suppose that $G$ is $k$-regular for some integer $k\ge 2\left\lceil\frac{1}{4}n\right\rceil-1$. 1-Factorization Conjecture. $G$ is 1-facto…

Let $G$ be a class 2 graph on $n$ vertices, and call a subgraph $H$ overfull when $|E(H)|>\Delta(H)\left\lfloor\frac{|V(H)|}{2}\right\rfloor$. Overfull conjecture. If…

Let $G$ be a cubic graph admitting a nowhere-zero $4$-flow. An edge $e$ is $4$-removable if $G-e$ has a nowhere-zero $4$-flow. Hoffmann-Ostenhof's conjecture. Every cubic graph adm…

Let $G$ be a graph with maximum degree $\Delta(G)$ and vertex set $V(G)$. A graph is overfull if $|E(G)|>\Delta(G)\lfloor |V(G)|/2\rfloor$, and a graph is Class 2 if its chromatic…

Let $S$ be a two-dimensional manifold, let $T$ be a triangulation of $S$, and let $G$ be the dual graph of $T$. Grünbaum's surface-coloring conjecture. The graph $G$ is $3$-edge-co…

Hilton–Zhao conjecture. If $\Delta(G_{\Delta})\leq 2$, then $G$ is overfull.

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…

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…

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…

Circular chromatic index conjecture. The graph $G$ satisfies

Burris–Schelp conjecture.

Let $K_n$ be the complete graph on $n$ vertices, with an edge-coloring that is $k$-bounded when no color appears on more than $k$ edges. A rainbow Hamiltonian cycle is a Hamiltonia…

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…

Let $G$ be a nice graph, meaning that it has no $K_2$ component. A proper edge-coloring is an edge-coloring in which adjacent edges receive different colors, and $\chi'_{\sum}(G)$…

Local-resilience conjecture. There exists a sufficiently large constant $C>0$ such that, whenever $G$ satisfies this local resilience condition and every Hamilton cycle in $G$ has…

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

Let $G$ be a bipartite graph whose two parts have maximum degrees $\Delta_1$ and $\Delta_2$, respectively. A strong edge coloring is an edge coloring in which every color class is…

Jakobsen's bounded-order conjecture. If

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

Let $G_1=(V,E_1)$ and $G_2=(V,E_2)$ be graphs on the same vertex set, each of maximum degree $Delta$, and let $chi(G_1,G_2)$ be the minimum number of colors in a simultaneous prope…

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

Local Irregularity Conjecture. Every connected graph $G\notin\mathfrak{T'}$ satisfies