Sudoku Number of Corona of Graphs

Manju S Nair; Aparna Lakshmanan S; S Arumugam

paper

Sudoku Number of Corona of Graphs

arXiv:2402.08933

Abstract

Let $G = (V, E)$ be a graph of order $n$ with chromatic number $χ (G) = k$ , let $S \subset V$ and let $C_{0}$ be a $k$ -coloring of the induced subgraph $G [S]$ . The coloring $C_{0}$ is called an extendable coloring, if $C_{0}$ can be extended to a $k$ -coloring of $G$ and it is a Sudoku coloring of $G$ if the extension is unique. The smallest order of such an induced subgraph $G [S]$ of $G$ which admits a Sudoku coloring is called the Sudoku number of $G$ and is denoted by $s n (G)$ . In this paper, we first introduce the notion of uniquely color extendable vertex and then we obtain the lower and upper bounds for the Sudoku number of $G \circ K_{1}$ . Some families of graphs which attain these bounds are also obtained. The exact value of the Sudoku number of corona of $C_{n}$ , $W_{n}$ and $K_{n}$ with $K_{1}$ and $C_{n} \circ P_{m}$ are also obtained.