This work generalizes and combines tools from the $(k+2)-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023] and yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.
Abstract
We prove that $k$-coloring on $n$-vertex graphs has a randomized algorithm running in time $(2-\varepsilon_k)^n$, where $\varepsilon_k>0$ for every fixed $k$. Previously, only the cases $k\leq 6$ were known to have faster solutions than the general $O^\star\bigl(2^n\bigr)$ time algorithm of [Bj\"{o}rklund, Husfeldt, Koivisto, SICOMP 2009] that computes the chromatic number. We resolve this long-standing open problem by generalizing and combining tools from the $(k+2)$-coloring to $k$-list-coloring reduction of [Zamir, ICALP 2021] and the hypergraph-containers based approach in [Zamir, STOC 2023]. Together with new algorithms for list-coloring instances mixing long and short color lists, this yields an iterable reduction from $(k+1)$-list-coloring to $k$-list-coloring over fixed palettes.
We show that for all $k$, there exists $\varepsilon_k>0$ such that graph $k$-coloring can be solved by a randomized algorithm with one-sided error in time $O((2-\varepsilon_k)^n)$. Prior to this work and independent concurrent work of Zamir [arXiv, 2026], exponential improvements over the $2^n \cdot \mathrm{poly}(n)$-time algorithm of Bj\"orklund, Husfeldt, and Koivisto [SIAM Journal on Computing, 2009] were only known for $k \le 6$.
The main result shows that the exact average-case complexity of this fundamental problem is $\Theta(nk)$ for every $k \leq n^{c'}$ and some $c'\in (0, 1)$, and reveals the average sublinear nature of $k$-colorability: the average-case complexity is linear in $n$, and thus sublinear in the size of the input.
Cassandra Marcussen, Edward Pyne, R. Rubinfeld et al.· 0 citations
We study the parameterized complexity of $k$-Coloring in $H$-free graphs, when $H$ is a linear forest (i.e., a disjoint union of paths) as an induced subgraph. We show two hardness results: * $k$-Coloring is W[1]-hard in $2P_2$-free graphs when parameterized by $k$. * $3$-Coloring is W[1]-hard in $P_t$-free graphs when parameterized by $t$. Moreover, assuming the ETH, these problems admit no algorithms solving $n$-vertex instances in time $f(k) \cdot n^{o(k)}$ and $f(t) \cdot n^{o(t/\log t)}$, respectively, for any computable function $f$. The first result resolves in a strong form a long-standing open problem, originally posed by Ho\`ang, Kami\'nski, Lozin, Sawada, and Shu [Algorithmica, 2010]. The second result answers a question of Golovach, Johnson, Paulusma, and Song [Journal of Graph Theory, 2017].
The first $poly(\Delta,\log n)-round algorithm for $(\Delta + 1)$-edge coloring in the CONGEST model is presented and the $n$-dependency of its runtime, $\tilde{O}(\log^5 n)$, matches the best published dependency in the LOCAL model.
Sebastian Brandt, Ananth Narayanan, Alexandre Nolin· 0 citations
The \emph{$k$-color Ramsey number} $R_k(C_{2\ell+1})$ is the least integer $n$ such that any $k$-edge-coloring of a complete graph $K_n$ has a monochromatic odd cycle $C_{2\ell+1}$. Axenovich, Cames van Batenburg, Janzer, Michel, and Rundstr\"om~(JCT-B, 2026) recently proved \[ R_k(C_{2\ell+1})\le (4\ell-2)^k k^{k/\ell}+1, \] and Miyazaki, Mulrenin, Pohoata, and Zheng further improved the factor $k^{k/\ell}$ to $(k!)^{1/\ell}$. As Jenssen and Skokan (AM, 2021) determined $R_k(C_{2\ell+1})$ for fixed $k$ and sufficiently large $\ell$, it becomes even more interesting to seek better bound for fixed $\ell$ and sufficiently large $k$. In this paper, we show \[ R_k(C_{2\ell+1}) \le \frac{2\ell}{2\ell-1}(2\ell-1)^k(k!)^{1/\ell} \exp\!\left(k^{1-1/\ell}+O_\ell\!\left(k^{1-2/\ell}+\log k\right)\right)+1 \] for every fixed $\ell\ge 2$ and sufficiently large $k$, which improves the bound of Miyazaki et al. by a factor $2^{k-o(k)}$, and the bound of Axenovich et al. by a factor $(2\e^{1/\ell})^{k-o(k)}$.
For an integer $k\geq2$, let $\chi_k'(G)$ denote the minimum number of colors in an edge-coloring of a graph $G$ such that every nonzero degree in each color subgraph is congruent to $1\pmod{k}$. A graph is a $0_k$-graph if every vertex degree is divisible by $k$. We disprove a conjecture of Berthe et al.\ (On modular edge colorings of graphs, SIAM J. Discrete Math. 40 (2026) 897--904), which states that $\chi_k'(G)\leq k+o(k)$ for every $0_k$-graph $G$. We prove a lower bound for $0_k$-graphs with degree set $\{k,2k\}$ and a specified vertex partition. With a suitable choice of the part sizes, if the number of edges inside one part is $o(k^2)$, then $\chi_k'(G)\geq(4-2\sqrt2+o(1))k$. This gives connected bipartite and connected nonbipartite counterexamples. In particular, the same examples also disprove the earlier conjecture of Botler, Colucci, and Kohayakawa (The mod $k$ chromatic index of graphs is $O(k)$, J. Graph Theory 102 (2023) 197--200), which states that $\chi_k'(G)\leq k+C$ for some absolute constant $C$.