30 problems

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…

Equitable coloring conjecture. If

Let $G$ be a connected graph, let $Delta(G)$ denote its maximum degree, and let an equitable $k$-coloring be a proper $k$-coloring whose color classes have sizes differing by at mo…

Equitable Coloring Conjecture. If $G$ is a connected graph that is neither a complete graph nor an odd cycle, then

Let $G$ be a $d$-degenerate graph with maximum degree at most $\Delta$. A proper coloring is equitable when its color classes differ in size by at most one. Kostochka–Nakprasit's c…

Equitable $\Delta$-Coloring Conjecture. For most connected graphs, the Hajnál–Szemerédi bound can be improved by one, with the extremal connected graphs characterized as $K_m$,…

Let $k\geq 1$ and let $G$ be a graph with $\Delta(G)\leq k$, where $\Delta(G)$ is the maximum degree. Every such graph is DP $(k+1)$-colorable and, by the Hajnal–Szemerédi theorem,…

Let $G$ be a graph, and let $\bDelta(G)$ denote its maximum degree. An equitable $k$-coloring is a proper $k$-coloring whose color classes differ in size by at most one. Erdős's co…

Let $B_1,\dots,B_k$ be the bases and let $T_1,\dots,T_\ell$ be pairwise disjoint sets in the setting of the source's equitability theorem. Akrami–Raj–Végh equitability conjecture.…

Let $n,k∈\mathbb{N}$ with $k≤n$. Let $G$ be an $n$-vertex graph whose degree sequence is $d_1≥⋯≥d_n$. Let an equitable $k$-coloring be a proper $k$-coloring whose color classes hav…

Let an equitable $k$-coloring be a proper $k$-coloring whose color classes have sizes differing by at most one, and let $d(x)$ denote the degree of a vertex $x$. Kierstead-Kostochk…

Let $G$ be a graph, let $d(x)$ denote the degree of a vertex $x$, and let an equitable $k$-coloring be a proper $k$-coloring whose color classes have sizes differing by at most one…

Five-color planar theorem conjecture. The same statement remains true when the lower bound $s\ge 40$ is replaced by $s\ge 5$.

Let $G$ be a series-parallel graph with maximum degree $\Delta$. A proper coloring is equitable when its color classes differ in size by at most one. Zhang–Wu's conjecture. If…

Let $L$ be a list assignment in which every vertex receives a list of size $k$. A graph is equitably $k$-choosable if every such assignment admits a proper $L$-coloring with each c…

Let $k\geq3$, and let a $k$-decomposition of a graph be a partition of its vertex set into induced subgraphs that are $k$-basic. Strong Chen–Lih–Wu conjecture. If $G$ is a $k$-colo…

Let $G$ be a connected graph, and let … Delta$(G)$-coloring. This conjecture is an equitable analogue of Brooks' theorem and concerns the equitable chromatic number. The paper's ab…

Let $G$ be an $r$-colorable graph, with maximum degree $\Delta(G)\leq r$. Let an $r$-list assignment $L$ assign $r$ available colors to each vertex, and call $G$ equitably $r$-choo…

Pancake graph equitable coloring conjecture. For every $n\geqslant 2$,

Let $G$ be a block graph. Write $\omega(G)$ for its clique number, $\alpha_{\min}(G)$ for the minimum size of a maximal independent set, and $\chi_{=}(G)$ for its equitable chromat…

Aperiodic Borel equitable Brooks conjecture. The graph $G$ has a $\mu$-equitable $\Delta$-coloring.

Chen--Lih--Wu's conjecture. The graph $G$ has an equitable $\Delta$-coloring unless one of the following holds: $\Delta=2$ and $G$ is an odd cycle; $G \cong K_{\Delta+1}$; or…

Let $G$ be a simple finite planar graph, and let $va^{\equiv}(G)$ denote its equitable vertex arborable threshold: the minimum integer $k$ such that $G$ admits an equitable tree-…

List $\Delta$-ECC. $G$ is equitably $k$-choosable for each $k\geq\Delta(G)$ if it is different from $K_m$, $C_{2m+1}$, and $K_{2m+1,2m+1}$.

List Hajnál–Szemerédi conjecture. Every graph $G$ is equitably $k$-choosable when $k\geq \Delta(G)+1$.