2025/05/08 by Manju S Nair, Nair, Manju S, Aparna Lakshmanan S +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Primary: 05C15 #Secondary: 05C76 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2505.04920
openalex publication_date 2025/05/08 · 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). Let k ≥ χ(G) and S ⊆ V. 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 k- Sudoku coloring of G, if C0 can be uniquely extended to a k-coloring of G. The smallest order of such an induced subgraph G[S] of G which admits a k- Sudoku coloring is called k- Sudoku number of G and is denoted by sn(G,k). When k=χ(G), we call k- Sudoku number of G as Sudoku number of G and is denoted by sn(G). In this paper, we have obtained the 3- Sudoku number of some bipartite graphs Pn, C2n, Km,n, Bm,n and G ∘ lK1, where G is a bipartite graph and l≥1. Also, we have obtained the necessary and sufficient conditions for a bipartite graph G to have sn(G,3) equal to n, n-1 or n-2. Also, we study the relation between k- Sudoku number of a graph G and the Sudoku number of a supergraph H of G.