2024/02/14 by Manju S Nair, Nair, Manju S, Aparna Lakshmanan S +3
Engineering · #05C15 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2402.08933
openalex publication_date 2024/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G = (V,E) be a graph of order n with chromatic number χ(G) = k, let S ⊂ V and let C0 be a k-coloring of the induced subgraph G[S]. The coloring C0 is called an extendable coloring, if C0 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 sn(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 ∘ K1. Some families of graphs which attain these bounds are also obtained. The exact value of the Sudoku number of corona of Cn, Wn and Kn with K1 and Cn ∘ Pm are also obtained.