论文标题
Sudoku图形数
Sudoku Number of Graphs
论文作者
论文摘要
我们介绍了由流行的Sudoku拼图激励的图形着色的新概念。令$ g =（v，e）$是订单$ n $的图形，带有色数$χ（g）= k $，让$ s \ subseteqv。$让$ \ mathscr c_0 $是$ k $ co $ k $ coloring诱导子级$ g [s]。 $ k $ - 颜色为$g。$我们说，如果$ \ mathscr c_0 $是$ g $的sudoku颜色，如果$ \ mathscr c_0 $可以独特地扩展到$ k $ col的$g。 $ sn（g）。$在本文中，我们启动了此参数的研究。我们首先表明此参数与图形列表着色有关。在第2节中，给出了与颜色主导的顶点，色数和顶点程度相关的Sudoku着色的基本特性。特别是，我们获得了$ \ mathscr c_0 $的必要条件，可独特地扩展，而$ \ mathscr c_0 $作为sudoku着色。在第3节中，我们确定了图形各种家族的Sudoku数量。特别是，我们证明了一个连接的图$ g $具有$ sn（g）= 1 $，并且仅当$ g $是双方时。因此，每个树$ t $都有$ sn（t）= 1 $。此外，带有小色调的图形$ g $可能具有任意较大的sudoku编号。可扩展的着色和Sudoku着色是提供$ g $的$ k $颜色的不错工具。
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\subseteq V.$ Let $\mathscr C_0$ be a $k$-coloring of the induced subgraph $G[S].$ The coloring $\mathscr C_0$ is called an extendable coloring if $\mathscr C_0$ can be extended to a $k$-coloring of $G.$ We say that $\mathscr C_0$ is a Sudoku coloring of $G$ if $\mathscr 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 $\mathscr C_0$ being uniquely extendable, and for $\mathscr C_0$ 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$.
