859 problems

Wang's conjecture. The D-coloring number of $G$ satisfies

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…

For any integer $t$ and any odd integer $k$, let $\mathcal{G}_{t,k}$ be the class of graphs that are $P_t$-free and whose induced odd cycles all have length $k$. Polynomial-time 3-…

Let $r$ and $s$ be integers, with $r$ even and $r\ge 2$, and $s$ odd and $s\ge 3$. Let $rFB(s)$ denote the corresponding flower-bouquet graph, and let $\chi_{la}(G)$ be the local a…

A fullerene nanodisc $D_r$ is a fullerene nanodisc indexed by an integer $r$. Type 1 conjecture. The fullerene nanodiscs $D_r$, for every integer $r\geq 2$, are Type 1. The conject…

Bipartition-respecting packing coloring conjecture. For every $n\geq 0$,

For a graph $G$, let $\chi(G)$ denote its chromatic number and let $\omega(G)$ denote its clique number. A graph is $P$-free if it contains no induced copy of the path $P$. Path-fr…

Higashitani–Matsumoto conjecture.

Path 3-colorability conjecture. Every path is matroidally $3$-colorable.

Let $G$ be a finite simple graph, let $c\geq 4$, and let $\operatorname{mad}(G)$ be its maximum average degree, defined by … An odd $c$-coloring is a proper $c$-coloring in which e…

Let $G$ be a graph with chromatic number $[?]{}$ and let $S\subseteq V(G)$ be colorful if every proper $\chi(G)$-coloring of $G$ assigns all $\chi(G)$ colors to vertices in $S$. An…

Faudree–Schelp–Gyárfás–Tuza conjecture. The following bounds hold:

Heroic-set conjecture. The set

Hedetniemi's conjecture.

All graphs are finite, simple, undirected graphs. Let $G$ be a graph and let $\sigma:E(G)\to\{-1,+1\}$ be a signature; the pair $(G,\sigma)$ is a signed graph, with underlying grap…

Let $k\geq 2$ and let $T$ be a tree. Write $\chi _{_{NL}}(T)$ for the neighbor-locating-chromatic number of $T$, and let $\Delta(T)$ denote its maximum degree. Maximum-degree conje…

Let $G$ be a planar graph and let $k$ be an integer. The $k$-recoloring graph $R_k(G)$ has vertices corresponding to proper $k$-colorings of $G$, with edges joining colorings that…

First signed path conjecture. For every pair of finite, binary trees $(D,R)$ with the same number of leaves, there is a sign assignment of $D$ and a word $w$ of rotation symbols va…

For a graph $G$ and a positive integer $k$, let $\chi_u(G,k)$ be the minimum number $t$ such that $G$ is uniquely $(k,t)$-list colorable, and let…

K4 subgraph conjecture. Every U$3$LC planar graph has $K_4$ as a subgraph.

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

Let $D$ be a finite set of positive integers, and let $\chi(D)$ denote the chromatic number of the distance graph with distance set $D$. For a fixed integer $k\ge3$, consider the d…

Let $G$ be an $n$-vertex graph with list-chromatic number $\chi_{\ell}$. For a positive integer $t\leq\chi_{\ell}$, assign each vertex a list of $t$ colors, and let $\lambda_t$ be…

Gap conjecture for the circular chromatic index. For every integer $k\geq 2$, there exists an $\epsilon>0$ such that no graph $G$ satisfies

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