Sudoku number of graphs
AbstractWe introduce a concept in graph coloring motivated by the popular Sudoku puzzle. Let [Formula: see text] be a graph of order n with chromatic number [Formula: see text] and let [Formula: see text] Let [Formula: see text] be a k-coloring of the induced subgraph [Formula: see text] The colorin...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2023-05-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | https://www.tandfonline.com/doi/10.1080/09728600.2023.2218917 |
| _version_ | 1797691172763729920 |
|---|---|
| author | J. Maria Jeyaseeli G. C. Lau W. C. Shiu S. Arumugam |
| author_facet | J. Maria Jeyaseeli G. C. Lau W. C. Shiu S. Arumugam |
| author_sort | J. Maria Jeyaseeli |
| collection | DOAJ |
| description | AbstractWe introduce a concept in graph coloring motivated by the popular Sudoku puzzle. Let [Formula: see text] be a graph of order n with chromatic number [Formula: see text] and let [Formula: see text] Let [Formula: see text] be a k-coloring of the induced subgraph [Formula: see text] The coloring [Formula: see text] is called an extendable coloring if [Formula: see text] can be extended to a k-coloring of G. We say that [Formula: see text] is a Sudoku coloring of G if [Formula: see text] can be uniquely extended to a k-coloring of G. The smallest order of such an induced subgraph [Formula: see text] of G which admits a Sudoku coloring is called the Sudoku number of G and is denoted by [Formula: see text] 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 [Formula: see text] being extendable, and for [Formula: see text] being a Sudoku coloring. In Section 3, we determined the Sudoku number of various families 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. We also proved that [Formula: see text] if and only if G = Kn. Moreover, a graph G with small chromatic number may have arbitrarily large Sudoku number. In Section 4, we proved that extendable partial coloring problem is NP-complete. Extendable coloring and Sudoku coloring are nice tools for providing a k-coloring of G. |
| first_indexed | 2024-03-12T02:09:31Z |
| format | Article |
| id | doaj.art-beede28d836b407489631233805ec6b6 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-03-12T02:09:31Z |
| publishDate | 2023-05-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-beede28d836b407489631233805ec6b62023-09-06T14:45:48ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742023-05-0120220921610.1080/09728600.2023.2218917Sudoku number of graphsJ. Maria Jeyaseeli0G. C. Lau1W. C. Shiu2S. Arumugam3National Centre for Advanced Research in Discrete Mathematics, Kalasalingam Academy of Research and Education, Krishnankoil, Tamil Nadu, IndiaFaculty of Computer & Mathematical Sciences, Universiti Teknologi MARA (Johor Branch, Segamat Campus), Segamat, MalaysiaDepartment of Mathematics, The Chinese University of Hong Kong, Shatin, Hong Kong, ChinaNational Centre for Advanced Research in Discrete Mathematics, Kalasalingam Academy of Research and Education, Krishnankoil, Tamil Nadu, IndiaAbstractWe introduce a concept in graph coloring motivated by the popular Sudoku puzzle. Let [Formula: see text] be a graph of order n with chromatic number [Formula: see text] and let [Formula: see text] Let [Formula: see text] be a k-coloring of the induced subgraph [Formula: see text] The coloring [Formula: see text] is called an extendable coloring if [Formula: see text] can be extended to a k-coloring of G. We say that [Formula: see text] is a Sudoku coloring of G if [Formula: see text] can be uniquely extended to a k-coloring of G. The smallest order of such an induced subgraph [Formula: see text] of G which admits a Sudoku coloring is called the Sudoku number of G and is denoted by [Formula: see text] 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 [Formula: see text] being extendable, and for [Formula: see text] being a Sudoku coloring. In Section 3, we determined the Sudoku number of various families 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. We also proved that [Formula: see text] if and only if G = Kn. Moreover, a graph G with small chromatic number may have arbitrarily large Sudoku number. In Section 4, we proved that extendable partial coloring problem is NP-complete. Extendable coloring and Sudoku coloring are nice tools for providing a k-coloring of G.https://www.tandfonline.com/doi/10.1080/09728600.2023.2218917Chromatic numberextendable coloringSudoku coloring05C7805C69 |
| spellingShingle | J. Maria Jeyaseeli G. C. Lau W. C. Shiu S. Arumugam Sudoku number of graphs AKCE International Journal of Graphs and Combinatorics Chromatic number extendable coloring Sudoku coloring 05C78 05C69 |
| title | Sudoku number of graphs |
| title_full | Sudoku number of graphs |
| title_fullStr | Sudoku number of graphs |
| title_full_unstemmed | Sudoku number of graphs |
| title_short | Sudoku number of graphs |
| title_sort | sudoku number of graphs |
| topic | Chromatic number extendable coloring Sudoku coloring 05C78 05C69 |
| url | https://www.tandfonline.com/doi/10.1080/09728600.2023.2218917 |
| work_keys_str_mv | AT jmariajeyaseeli sudokunumberofgraphs AT gclau sudokunumberofgraphs AT wcshiu sudokunumberofgraphs AT sarumugam sudokunumberofgraphs |