



























The Sudoku number $s(G)$ of graph $G$ with chromatic number $χ(G)$ is the smallest partial $χ(G)$-colouring of $G$ that determines a unique $χ(G)$-colouring of the entire graph. We show that the Sudoku number of the random $3$-regular graph $\mathcal{G}_{n,3}$ satisfies $s(\mathcal{G}_{n,3}) \leq (1+o(1))\frac{n}{3}$ asymptotically almost surely. We prove this by analyzing an algorithm which $3$-colours $\mathcal{G}_{n,3}$ in a way that produces many locally forced vertices, i.e., vertices which see two distinct colours among their neighbours. The intricacies of the algorithm present some challenges for the analysis, and to overcome these we use a non-standard application of Wormald's differential equations method that incorporates tools from finite Markov chains.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。