2022/06/16 by Gee-Choon Lau, J. Maria Jeyaseeli, Lau, Gee-Choon +5
Computer Science · Engineering · #05C69 #05C78 #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2206.08106
openalex publication_date 2022/06/16 · openalex created_date 2022/06/19 · openalex updated_date 2026/07/28
We introduce a new concept in graph coloring motivated by the popular Sudoku puzzle. Let G=(V,E) be a graph of order n with chromatic number χ(G)=k and let S⊆ V. Let \mathscr C0 be a k-coloring of the induced subgraph G[S]. The coloring \mathscr C0 is called an extendable coloring if \mathscr C0 can be extended to a k-coloring of G. We say that \mathscr C0 is a Sudoku coloring of G if \mathscr 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 Sudoku coloring is called the Sudoku number of G and is denoted by sn(G). In this paper we initiate a study of this parameter. We first show that this parameter is related to list coloring of graphs. In Section 2, basic properties of Sudoku coloring that are related to color dominating vertices, chromatic numbers and degree of vertices, are given. Particularly, we obtained necessary conditions for \mathscr C0 being uniquely extendable, and for \mathscr C0 being a Sudoku coloring. In Section 3, we determined the Sudoku number of various familes of graphs. Particularly, we showed that a connected graph G has sn(G)=1 if and only if G is bipartite. Consequently, every tree T has sn(T)=1. Moreover, a graph G with small chromatic number may have arbitrarily large Sudoku number. Extendable coloring and Sudoku coloring are nice tools for providing a k-coloring of G.