1,435 problems

Let $G$ be a planar graph with maximum degree $\Delta$, and let $\chi_2(G)$ denote the minimum number of colors in a coloring in which vertices at distance at most $2$ receive dist…

Let $G$ be a graph, with maximum degree $\Delta(G)$ and clique number $\omega(G)$. Reed's conjecture. Every graph $G$ satisfies … This refines the Borodin–Kostochka direction and i…

Gyárfás's conjecture. The family of odd-hole-free graphs, the family of graphs with no hole of length at least $\ell$, and the family of graphs with no odd hole of length at least…

Kneser's conjecture. The chromatic number of $\operatorname{Kn}(q,k)$ is

A planar graph without cycles of length 4 or 5 is a planar graph containing no cycle of length $4$ or $5$. Steinberg's conjecture. Every planar graph without cycles of length $4$ o…

Chen–Lih–Wu conjecture. Every connected graph $G$ with maximum degree $\Delta \geq 2$ admits an equitable coloring with $\Delta$ colors, except when $G$ is a complete graph, an odd…

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ denote its chromatic number, $\omega(G)$ its clique number, and $\Delta(G)$ its maximum deg…

Total Coloring Conjecture. For every graph $G$,

Cereceda's conjecture. For any $d$-degenerate graph $G$ and $d+2$, the diameter of $$ is $O(n^2)$.

Let ${\mathcal C}$ be a hereditary graph class, and suppose that ${\mathcal C}$ is chi-bounded, meaning that its chromatic number is bounded by a function of its clique number. Esp…

Grünbaum's conjecture. Every planar graph admits an acyclic coloring with $5$ colors.

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…

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

Fox–Grinshpun–Pach conjecture.

Thomassen's conjecture. Every such graph $G$ admits a crumby red-blue vertex coloring.

Let $G$ be a claw-free graph, and let $\chi_\ell(G)$ denote its list chromatic number and $\operatorname{\Delta_2}(G)$ its maximum codegree. The claw-free list-coloring conjecture.…

List Coloring Conjecture. Every line graph of a loopless multigraph is chromatic-choosable.

Let $R$ be a finite chromatic ring, and let $\Gamma(R)$ be its zero-divisor graph. Write $\omega(\Gamma(R))$ for the clique number of $\Gamma(R)$ and $\chi(\Gamma(R))$ for its chro…

Tucker's Infinite Motion Conjecture. Every connected, locally finite graph with infinite motion admits an asymmetric 2-coloring.

Let $k\geqslant 5$ be an integer. For a graph $G$, write $\chi_2(G)$ for its 2-distance chromatic number, $\Delta(G)$ for its maximum degree, and say that $G$ has girth at least…

Brualdi–Quinn Massey conjecture. For any bipartite graph $G$ with partite sets $A$ and $B$,

For a positive integer $k$, let $f(k)$ be the maximum possible chromatic number of a graph whose edge set can be partitioned into at most $k$ complete bipartite graphs, and set…

Plummer–Zha conjecture. Every pentagraph is $3$-colorable.

Let $G$ be a graph without isolated edges. An edge coloring $f:E\to\{1,2,\dots,k\}$ assigns a weight $\sigma(v)=\sum_{v\in e}f(e)$ to each vertex; adjacent vertices are distinguish…

Let $G$ be a simple graph, let $\Delta(G)$ denote its maximum degree, and let $\chi_T(G)$ denote its total chromatic number, the minimum number of colors in a total coloring of $G$…