广义彼得森图和贾汉吉尔图的对策色数

摘要

让 是一个图，两个玩家Alice和Bob轮流给图的顶点着色一种正确的上色，没有两个相邻的顶点用相同的颜色签名。Alice的目标是使用最小的颜色数来着色顶点集合，这被称为游戏色数，表示为 ,而鲍勃的目标是阻止爱丽丝的目标。本文研究了博弈色数问题广义彼得森图的研究 为 和任意 , -交叉棱镜图和贾汉吉尔图 。

1.介绍

1981年，Brams发明了该游戏，作为一种工具，在不使用计算机的情况下提供四色定理的理论证明[1]。但是，很明显，有许多平面图的对策色数大于4。1991年，博德兰恩德将乒乓球重新发明为两人比赛，爱丽丝和鲍勃。2]。玩家轮流给给定的有限图的顶点着色 还有一套颜色 。交替地，玩家轮流使用一组元素 ;Alice开始游戏，她的目标是用only为顶点着色 而鲍勃的目标是阻止她。如果在任何阶段有一些顶点没有可用的颜色，Bob将赢得游戏。图的对策色数 ,用 ,被定义为最小的整数这样爱丽丝就有了获胜的策略颜色。在[3.， Faigle等人证明了这一点 对于树形图。在[4， Guan和Zhu引入了外平面图的对策色数的上界，即 。在[5， Bartnicki等人研究了两个图的笛卡儿积的对策色数。在[6， Sia研究了笛卡尔积图的一些族的博弈。拉波特和吴证明了这一点 (7]。

在[8， Shaheen等研究了一些特殊循环图和广义彼得森图的对策色数 。

颜色数量在[9]如下:

让是图的顶点集上的线性序的集合G,让 。为一个顶点 ,后面的程度的关于它的邻居的数量在它之前吗 ,也就是说, 在哪里 。后度顶点的最大回度是多少 。的上色数用是1 +在哪里线性排序的最小回退度是多少对所有 ,也就是说, 。很明显, 。

游戏着色数 是着色数的竞争版本，是朱在[10]给出了一个改进的平面图对策色数上界。上色数游戏是一个两人游戏，由爱丽丝和鲍勃轮流玩，爱丽丝先开始。在每次移动之后，选择一个顶点(在剩余的顶点中)，并将其添加到之前移动形成的线性排序的末尾。选择了所有的顶点后，进行线性排序的了,让是它的后度，然后 。Alice的目标是最小化回度 ,而Bob的目标是最大化它。双方都使用他们的最佳策略来形成 。

一个组合游戏是具有完全信息和无机会的有限两方博弈。博弈色数与博弈色数是组合博弈[11]。

2009年，Kierstead和Kostochka率先将着色游戏应用于一个nongame问题，即图形包装问题[12]。

2019年提出了一些研究，讨论了一些特定图的博弈色数[11,13,14]。在[14C. Chamberlin等研究了的博弈色数G每条边细分后的图是哪一条 与足够大, 。

本色的顶点被称为关键的顶点如果只有一种颜色的话还有一些没有颜色的邻居哪一个可以签 。在游戏的任何阶段，如果在Bob的回合中有一些关键的顶点，那么他将赢得游戏。同样，如果在Alice的回合中有关键顶点，那么她必须通过她的回合[来保护它们。7]。

我们表示艾丽丝被和表示分配顶点的过程的颜色通过 。

两个顶点是相邻的，如果有一条边把它们连接在一起。为一个顶点图中 ,开邻居集被定义为 和的程度的是 。一个图表 是常规的如果 对于每一个 。

定义1。让整 满足 ;广义彼得森图 这个图的顶点集是 在哪里 和 它的边集是 ,在哪里 下标是约模的n。

定义2。对于一个正的偶数 , -交叉棱镜图 图是由两个不同的循环，外循环得到的吗在哪里 ,里面的那个在哪里 在它们之间加上边 。

定义3。贾汗季图,为 ,是一个周期添加一个顶点毗邻顶点的它们在远处彼此远离 。

定义4。的 -sunlet图是一个周期在哪里 与额外的顶点 ,和 为 。

建议1(见[10])。 。

建议2(见[15])。的博弈色数轮图 是 。

定理1(见[8])。为 和 ,我们有 。

2.主要结果

在本节中，我们研究了广义彼得森图的对策色数， -交叉棱镜图和贾汉吉尔图。

引理1。为 和 ,每个广义彼得森图 有作为一个子图，就像图中的图1。

这个证明来自广义彼得森图的定义。

定理2。为 ,广义彼得森图的对策色数 是 。

证明。广义彼得森图是三正则图;因此, 。为 , 用定理证明1。
现在，反过来，我们要证明玩家A对于任意整数没有任何获胜策略 。
假设我们有一个颜色集 ;通过使用引理2.1，我们注意到，在 ,有如图中的图所示的子图1。
无论玩家A在开始时选择了什么顶点，我们都会得到相同的状态，所以在不失一般性的前提下假设玩家A在游戏开始时是这样的 ,也就是说, 然后 ;现在,一个关键顶点，所以玩家a会用第三种颜色给它上色或者用合法的颜色给它唯一的未上色的邻居上色来保护它吗是,那么 也就是说这个顶点将成为一个关键顶点，同时球员a将不得不捍卫它，所以无论他的选择是什么然后 现在有两个关键顶点 玩家A不能一起防守所以三种颜色不足以让第一个玩家有获胜的策略。然后, 。

定理3。 ,让是一个 -交叉棱柱图，和博弈色数的是 。

证明。 自 ;因此，我们要反驳三种颜色是不够的。让 和 ;然后, ,现在,是一个关键顶点，所以Alice只能用两种方法来保护它。我们将讨论爱丽丝的第二次回合如下:案例1。 然后 ,这就给出了两个关键顶点 爱丽丝不能同时为他们辩护案例2。 在哪里 子用例2.1。 然后 然后 将是关键顶点而Alice不能同时保护它们子用例2.2。 然后轮到鲍勃的时候谁会变成关键顶点颜色是3，爱丽丝输了这意味着 ,所以

定理4。为 ,让 就是贾汉吉尔图，和博弈的色数

证明。首先，因为Jahangir图可以划分为循环，那么就很容易表明 。现在，我们将讨论以下情况。案例1。 子用例1.1。 然后 ,和使用建议1, 。子用例1.2。 和 那么三种颜色是不够的因为如果我们假设颜色集合 和 然后 ,然后会有两个关键顶点 ,爱丽丝下一轮不能一起防守他们，所以她输了游戏。例2。 子用例2.1。当 ,如图所示2。如果 和 ,Alice可以用三种颜色保护任何关键顶点，即使是用在子情况1.2中提到的Bob策略。我们可以这样解释Alice的获胜策略:设颜色为 和 然后 ,所以会有两个关键顶点 ,然后当爱丽丝选择下一步 ;因此，Bob不能在顶点上使用颜色3 赢了这个游戏，爱丽丝赢了，只有三种颜色。子用例2.2。当 。我们将利用博弈着色数作为工具来研究的上界 。
让 和 。所选顶点集为 。
一开始，Alice选择了中心顶点 。Bob选择一个顶点 。Alice遵循下一个策略来回应。(1)如果 然后爱丽丝补充道来(2)其他的,如果 和 然后爱丽丝选择并将其添加到(3)否则，Alice选择任何未选择的顶点使用这个策略以防 产生一个最优线性顺序与恢复程度 。所以, ,然后, 通过使用命题1。因此, 自 。

的利益冲突

作者声明，他们没有利益冲突。

致谢

这项工作得到了叙利亚Tishreen大学理学院的支持。

参考文献

1. T. Bartnicki, J. Grytczuk, H. A. Kierstead和X. Zhu，《地图着色游戏》，《美国数学月刊》第114卷第1期9，第793-803页，2007。视图:出版商的网站|谷歌学术搜索
2. h·l·博德兰德(H. L. Bodlaender)，《论一些着色游戏的复杂性》(On the complexity of some colour games)，国际计算机科学基础杂志第2卷第1期2，第133-147页，1991。视图:出版商的网站|谷歌学术搜索
3. 《论若干类图的博弈色数》，m . Faigle, m . Kem, H. Kierstead, W. T. Trotter， <论若干类图的博弈色数>，Ars Combinatorica，第35卷，第143-150页，1993年。视图:谷歌学术搜索
4. 关、朱，“外平面图的博弈色数”，图论杂志第30卷，no。1，第67-70页，1999。视图:谷歌学术搜索
5. t . Bartnicki b . Brešar j . Grytczuk m . Kovše z Miechowicz, i Peterin,“游戏彩色数量的笛卡儿积图,电子,”组合理论杂志， 2008年第15卷。视图:出版商的网站|谷歌学术搜索
6. 《笛卡儿积图若干族的对策色数》，国际图形和组合学杂志第6卷，no。2009年，第315-327页。视图:谷歌学术搜索
7. A.拉索和J.吴，《圆环网格的游戏色数》，信息处理信件第109卷，不。21-22，第1183-1186页，2009年。视图:出版商的网站|谷歌学术搜索
8. 《一些正则图的对策色数》，《规则图的对策色数》。开放离散数学杂志，第9卷，no。2019年，第159-164页。视图:出版商的网站|谷歌学术搜索
9. H. A. Kierstead和D. Yang，《图形的排序与博弈着色数》，Kluwer学术出版社，第10卷，第255-264页，2003年。视图:出版商的网站|谷歌学术搜索
10. 朱，“平面图形着色数的博弈”，组合理论杂志，B系列第75卷，no。2，第245-258页，1999。视图:出版商的网站|谷歌学术搜索
11. A. Furtado, S. Dantas, C. de Figueiredo，和S. Gravier，“毛虫的游戏色数4，”理论计算机科学的电子笔记，第346卷，第461-472页，2019年。视图:出版商的网站|谷歌学术搜索
12. H. A. Kierstead和A. V. Kostochka，《通过游戏着色的有效图形包装》，组合学，概率和计算，第18卷，第765-774页，2009。视图:谷歌学术搜索
13. 《路径与循环分裂图的博弈色数》，国立台湾师范大学出版社，2002年。理论计算机科学，第795卷，第50-56页，2019年。视图:谷歌学术搜索
14. 钱伯林，J. DeCapua, H. Elser, D. Gerraputa，和A. Hamm，“关于密切尔斯定理和布鲁克斯定理的对策色数类比”，北卡罗莱纳数学与统计杂志，第5卷，第17-27页，2019年。视图:谷歌学术搜索
15. c.j. Destacamento, a.d. Rodriguez和l.a. Ruivivar，若干类图的博弈色数，DLSU研究大会2014年，De La Salle University, Manila, PH, USA。

版权

Ramy Shaheen等人版权所有这是一篇开放获取下发布的文章知识共享署名许可，允许在任何媒体中不受限制地使用、发布和复制原创作品，只要原稿被正确引用。