























Given a graph $G$, a colouring of $G$ is \emph{acyclic} if it is a proper colouring of $G$ and every cycle contains at least three colours. Its acyclic chromatic number $χ_a(G)$ is the minimum~$k$ such that an acyclic $k$-colouring of $G$ exists. When $G$ has maximum degree $Δ$, it is known that $χ_a(G) = \mathcal {O}(Δ^{4/3})$ as $Δ\to \infty$, and that $χ_a(G) = \mathcal {O}(\sqrt{t} \cdot Δ)$ if in addition $G$ does not contain $K_{2,t}$ as a subgraph. We study the extremal value of the acyclic chromatic number in the class of graphs of maximum degree $Δ$ that do not contain some fixed subgraph $F$ on $t$ vertices. We establish that this extremal value is at most $\mathcal {O}(t^{8/3}Δ^{2/3})$ if $F$ is a tree, $\mathcal {O}(\sqrt{t} \cdot Δ)$ if $F$ is bipartite and can be made acyclic with the removal of one vertex, $2Δ+ \mathcal {O}(tΔ^{2/3})$ if $F$ is an even cycle of length at least $6$, and $\mathcal {O}(t^{1/4}Δ^{5/4})$ if $F=K_{3,t}$. Moreover, we exhibit an infinite family of obstructions $F$ that each induces a different asymptotic behaviour 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 $G(n,p)$ or $G(n,n,p)$, that we entirely determine up to a ${\rm polylog}(n)$ factor. As a byproduct, we can certify that most of our results are tight up to a $Δ^{\mathcal{O}(1/t)}$ factor.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。