Playing Sudoku on random 3-regular graphs

Abstract

The Sudoku number $s(G)$ of graph $G$ with chromatic number $\ddot{I}‡(G)$ is the smallest partial $\ddot{I}‡(G)$-colouring of $G$ that determines a unique $\ddot{I}‡(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})\le (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.