The k k - Sudoku Number of Graphs

Manju S Nair, Aparna Lakshmanan S, S Arumugam · 2025

Read The k k - Sudoku Number of Graphs by Manju S Nair, Aparna Lakshmanan S, S Arumugam (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-04920.txt.

Introduction

Manju Nair, Aparna Lakshmanan, and S. Arumugam study a puzzle idea that mixes Sudoku with graph coloring. In graph theory, coloring means assigning labels to points so that linked points differ. A partial coloring is called a Sudoku coloring if it can be completed to a full coloring in exactly one way. The smallest partial coloring with that trait is the graph's Sudoku number, and the paper works out this number for several families of graphs.

The authors focus on bipartite graphs, whose points split into two sets with links only between sets. They find the number for paths, even cycles, complete two-part graphs, and some related forms. They also give exact conditions for when a bipartite graph's number equals its full point count or falls just one or two below it. A final section links a graph's number to that of a larger graph containing it.

Catalog record

CREATORManju S Nair, Aparna Lakshmanan S, S Arumugam
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-04920

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The k k - Sudoku Number of Graphs Manju S Nair, Aparna Lakshmanan S, S Arumugam Abstract AMS Subject Classification: Primary: 05C15, Secondary: 05C76 1 Introduction By a graph G=(V,E) , we mean a finite undirected connected simple graph of order n(G)=|V| and size m(G)=|E| (if there is no ambiguity in the choice of G , then we write it as n and m , respectively). A vertex coloring of G is a map f:V\rightarrow C , where C is a set of distinct colors. It is proper if adjacent vertices of G receive distinct colors of C , that is, if uv\in E(G) , then f(u)\neq f(v) . The minimum number of colors needed for a proper vertex coloring of G is called the chromatic number \chi(G) , of a graph G . The concept of Sudoku coloring has been developed recently in graph coloring motivated by the famous Sudoku puzzle. A solution to a Sudoku puzzle represents a proper vertex coloring of a graph G using 9 colors with vertex set V containing 81 cells where each of the 9 rows, 9 columns and nine 3 x 3 subsquares are complete graphs. To solve the puzzle, some of the cells will be initially filled with numbers 1 to 9. In otherwords, a proper vertex coloring C of an induced subgraph H of G will be initially given using atmost 9 colors and that can be uniquely extended to a proper 9-coloring of G . This gave the idea of Sudoku coloring of a graph G [ 7 ] . Let \chi(G)=k and S\subset V . 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 . C_{0} is a Sudoku coloring of G , if this 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) [ 7 ] . A bistar graph is a graph formed by joining the center vertices of two star graphs K_{1,m} and K_{1,n} by an edge and is denoted by B(m,n) . The cycle and path on n vertices are denoted by C_{n} and P_{n} respectively and K_{m,n} represents the complete bipartite graph with partite sets of cardinality m and n . In particular, K_{1,n} is called a star. The corona product of two graphs G and H , denoted by G\circ H , is defined as the graph obtained by taking one copy of G and |V(G)| copies of H and joining the i^{\text{th}} vertex of G to every vertex in the i^{\text{th}} copy of H . Though various authors had dealt with the concept of Sudoku number under various names like critical sets, defining sets etc, only few papers are available in literature. Interested readers may refer to [ 2 ] , [ 4 ] , [ 5 ] , [ 6 ] , [ 7 ] and [ 8 ] . In [ 3 ] , Stijn Cambie has extended the notion sn(G) to k -coloring where k>\chi(G) and denoted the new parameter by sn(G,k) . Since only a few results are done on this parameter, we had done a detailed study on sn(G,k) in our paper. As the same name Sudoku number is used in [ 3 ] for both the parameters sn(G) and sn(G,k) , to avoid confusion, we call sn(G,k) as k - Sudoku number in our paper. In the paper, we determined the 3 - Sudoku number of some bipartite graphs. 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 . For notations and concepts not mentioned here, we refer to [ 1 ] Definition 1.1 . Let G=(V,E) be a graph of order n with chromatic number \chi(G) . Let k\geq\chi(G) and S\subseteq V . 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 k - Sudoku coloring of G , if C_{0} 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=\chi(G) , we call k - Sudoku number of G as Sudoku number of G and is denoted by sn(G) . The following lemmas and definition are useful for us. Lemma 1.1 . Let G be a graph with \chi(G)\geq 3 . Suppose C_{0} is an extendable coloring of G[S] for S\subset V(G) . If there is a pendant vertex v\notin S , then C_{0} is not a Sudoku coloring [ 7 ] . Lemma 1.2 . Let G be a graph with \chi(G)=k\geq 3 . Suppose C_{0} is an extendable coloring of G[S] for S\subset V(G) . If there is an edge xy for which x,y\notin S such that deg( x ) \leq k-1 and deg( y ) \leq k-1 , then C_{0} is not a Sudoku coloring [ 7 ] . Lemma 1.3 . Let L(x_{i}) be a list of colors of a vertex x_{i} in the path P_{n}=x_{1}x_{2}\dots x_{n} , 1\leq i\leq n . If |L(x_{i})|\geq 2 for each i , then there are at least 2 list colorings of P_{n} [ 7 ] . Lemma 1.4 . Suppose there exists a list coloring of the cycle C_{n}=v_{1}v_{2}\dots v_{n}v_{1} such that the list of colors for each vertex v_{i} satisfies the following conditions. • |L(v_{i})|\geq 2 • L(v_{i})\subseteq\{1,2,3\} Then there are at least two list colorings of C_{n} [ 7 ] . 2 3 - Sudoku number of some bipartite graphs The following theorem establishes the exact value of 3 - Sudoku number of various subclasses of bipartite graphs. Theorem 2.1 . The 3 - Sudoku number of (i) the path P_{n} is \lceil\frac{n+1}{2}\rceil . (ii) the even cycle C_{2n} , where n\geq 2 , is n . (iii) the star graph K_{1,n} , where n\geq 2 , is n . (iv) the complete bipartite graph K_{m,n} , where 2\leq m\leq n , is m . (v) the bistar B_{m,n} is m+n , except for m=n=1 and sn(B_{1,1},3)=3 . Proof. (i) Let v_{1},v_{2},\dots,v_{n} denote the vertices of P_{n} . For any initial coloring of P_{n} using 3 colors, the two pendant vertices of P_{n} must be initially colored. Also, since the degree of the remaining vertices is 2 , atleast one vertex from each edge must also be initially colored. Hence, sn(P_{n},3)\geq\lceil\frac{n+1}{2}\rceil . Now, let C be the initial coloring of P_{n} defined as follows. When n is odd, color the vertices v_{1},v_{3},\dots,v_{n} with colors 1 and 2 alternately. When n is even, color the vertices v_{1},v_{3},\dots,v_{n-1} with colors 1 and 2 alternately and v_{n} with

Read the complete text