24 problems

Let $G$ be a graph, let $k$ be a positive integer, and let $L$ be a $k$-list assignment for $G$. Write $m:=\left\lceil\frac{|G|}{k}\right\rceil$. An $L$-coloring is $m$-bounded if…

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…

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

Equitable coloring conjecture. If

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 graph with maximum degree $\Delta(G)$, and let a $k$-equitable coloring be a proper coloring with $k$ color classes whose sizes differ by at most one. Grünbaum's conje…

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

Let $G$ be a graph and let $T(G)$ be its total graph, whose vertices represent the vertices and edges of $G$. An equitable $k$-coloring is a proper $k$-coloring whose color classes…

Let $G$) be a connected graph, and let $\Delta(G)$ denote its maximum vertex degree. An equitable $k$-coloring is a proper coloring whose color classes differ in size by at most…

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

The $\Delta$-ECC. $G$ is equitably $\Delta(G)$-colorable if it is different from $K_m$, $C_{2m+1}$, and $K_{2m+1,2m+1}$.

For a graph $G$, let $\Delta(G)$ denote its maximum degree and let $\chi_e^*(G)$ be the smallest integer $k$ such that $G$ is equitably $l$-colorable for every $l\geq k$. Chen–Lai–…

Let $G$ be a finite simple graph, let $T(G)$ be its total graph, and let $\chi_l(T(G))$ denote the list chromatic number of $T(G)$. A graph is equitably $k$-choosable if every list…

Let $\Delta$ be an integer, let $d\in\{2,\dotsc,\Delta\}$, and let $G$ be a $d$-degenerate graph with maximum degree at most $\Delta$. An equitable coloring is a proper vertex colo…

Let $G$ be a graph. A graph is $k$-equitable if $|G|=ks$, $\chi(G)\le k$, and every proper $k$-coloring of $G$ has $s$ vertices in each color class. Write $H_1+H_2$ for the disjoin…

Let $G$ be a connected graph. A proper equitable $t$-coloring is a proper vertex coloring whose color classes differ in size by at most one, and $\chi^{=}(G)$ is the least $t$ for…