Abstract. Given a graph [Formula: see text], a coloring of [Formula: see text] is acyclic if it is a proper coloring of [Formula: see text] and every cycle contains at least three colors. Its acyclic chromatic number [Formula: see text] is the minimum [Formula: see text] such that an acyclic [Formula: see text]-coloring of [Formula: see text] exists. When [Formula: see text] has maximum degree [Formula: see text], it is known that [Formula: see text] as [Formula: see text] and that [Formula: see text] if, in addition, [Formula: see text] does not contain [Formula: see text] as a subgraph. We study the extremal value of the acyclic chromatic number in the class of graphs of maximum degree [Formula: see text] that do not contain some fixed subgraph [Formula: see text] on [Formula: see text] vertices. We establish that this extremal value is at most [Formula: see text] if [Formula: see text] is a tree, [Formula: see text] if [Formula: see text] is bipartite and can be made acyclic with the removal of one vertex, [Formula: see text] if [Formula: see text] is an even cycle of length at least 6, and [Formula: see text] if [Formula: see text]. Moreover, we exhibit an infinite family of obstructions [Formula: see text] that each induces a different asymptotic behavior for this extremal value. This is obtained with the derivation of lower bounds that come from the analysis of the acyclic chromatic number of a random graph drawn from either [Formula: see text] or [Formula: see text], which we entirely determine up to a [Formula: see text] factor. As a byproduct, we can certify that most of our results are tight up to a [Formula: see text] factor.

We analyse uniformly random proper k-colourings of sparse graphs with maximum degree Δ in the regime Δ < klnk . This regime corresponds to the lower side of the shattering threshold for random graph colouring, a paradigmatic example of the shattering threshold for random Constraint Satisfaction Problems. We prove a variety of results about the solution space geometry of colourings of fixed graphs, generalising work of Achlioptas and Coja-Oghlan, and Molloy on random graphs, and justifying the performance of stochastic local search algorithms in this regime. Our central proof relies only on elementary techniques, namely the first-moment method and a quantitative induction, yet it strengthens list-colouring results due to Vu, and more recently Davies, Kang, P., and Sereni, and generalises state-of-the-art bounds from Ramsey theory in the context of sparse graphs. It further yields an approximately tight lower bound on the number of colourings, also known as the partition function of the Potts model, with implications for efficient approximate counting.

We introduce a new method for computing bounds on the independence number and fractional chromatic number of classes of graphs with local constraints and apply this method in various scenarios. We establish a formula that generates a general upper bound for the fractional chromatic number of triangle-free graphs of maximum degree $\Delta \ge 3$. This upper bound matches that deduced from the fractional version of Reed's bound for small values of $\Delta$, and improves it when $\Delta\ge 17$, transitioning smoothly to the best possible asymptotic regime, barring a breakthrough in Ramsey theory. Focusing on smaller values of $\Delta$, we also demonstrate that every graph of girth at least $7$ and maximum degree $\Delta$ has fractional chromatic number at most $1+ \min_{k \in \mathbb{N}} \frac{2\Delta + 2^{k-3}}{k}$. In particular, the fractional chromatic number of a graph of girth $7$ and maximum degree $\Delta$ is at most $\frac{2\Delta+9}{5}$ when $\Delta \in [3,8]$, at most $\frac{\Delta+7}{3}$ when $\Delta \in [8,20]$, at most $\frac{2\Delta+23}{7}$ when $\Delta \in [20,48]$, and at most $\frac{\Delta}{4}+5$ when $\Delta \in [48,112]$. In addition, we also obtain new lower bounds on the independence ratio of graphs of maximum degree $\Delta \in \{3,4,5\}$ and girth $g\in \{6,\dotsc,12\}$, notably $1/3$ when $(\Delta,g)=(4,10)$ and $2/7$ when $(\Delta,g)=(5,8)$.

Alon and Mohar (2002) posed the following problem: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$th power of $G$? For $t\ge 3$, we provide several upper and lower bounds concerning this problem, all of which are sharp up to a constant factor as $d\to \infty$. The upper bounds rely in part on the probabilistic method, while the lower bounds are various direct constructions whose building blocks are incidence structures.