Sudoku number of graphs

Abstract

We introduce a concept in graph coloring motivated by the popular Sudoku puzzle. Let $G=(V,E)$ be a graph of order n with chromatic number $\chi (G)=k$ and let $S\subseteq V.$ Let ${\mathcal{C}}_0$ be a k-coloring of the induced subgraph $G[S].$ The coloring ${\mathcal{C}}_0$ is called an extendable coloring if ${\mathcal{C}}_0$ can be extended to a k-coloring of G. We say that ${\mathcal{C}}_0$ is a Sudoku coloring of G if ${\mathcal{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 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 ${\mathcal{C}}_0$ being extendable, and for ${\mathcal{C}}_0$ 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 $sn(G)=|V(G)|-1$ if and only if G = K_n. 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.

KEYWORDS:

• Chromatic number
• extendable coloring
• Sudoku coloring

2010 AMS SUBJECT CLASSIFICATION:

• 05C78
• 05C69

Acknowledgments

The authors are thankful to Stijn Cambie and Bernardo Anibal Subercaseaux Roa for their helpful suggestions in proving Theorems 3.5 and 4.2, respectively.