设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投稿
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematics应用数学进展,2023,12(4),1504-1509
PublishedOnlineApril2023inHans.https://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2023.124156
乘积图的博弈染色数
苏苏苏俊俊俊义义义
浙江师范大学数学科学学院，浙江金华
收稿日期：2023年3月13日；录用日期：2023年4月9日；发布日期：2023年4月19日
摘要
本文讨论的图是 两棵树的乘积图.分别研究了树和 树的笛卡尔积图、直积图和强积图 的(𝑎,1)-博弈
染色数,给出了三种乘积图的(𝑎,1)-博弈染色的上界.特殊地,如果其中一棵树是一条路,那么我们
类似的可以得出关于树和路的乘积图的(𝑎,1)-博弈染色数的结果.
关键词
笛卡尔积图，直积图，强积图，博弈染色数
TheGameColoringNumberofProduct
Graph
JunyiSu
SchoolofMathematicalScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Mar.13
𝑡ℎ
,2023;accepted:Apr.9
𝑡ℎ
,2023;published:Apr.19
𝑡ℎ
,2023
Abstract
Thegraphdiscussedinthisarticleisaproductgraphoftwotrees.Westudythe
(𝑎,1)-gamecoloringnumbersoftheCartesianproductgraph,directproductgraph
andstrongproductgraphsoftwotrees,andgivetheupperboundsof(𝑎,1)-game
文章引用:苏俊义.乘积图的博弈染色数[J].应用数学进展,2023,12(4):1504-1509.
DOI:10.12677/aam.2023.124156
苏俊义
coloringnumbersofthethreeproductgraphs.Inparticular,ifoneofthetreesisa
path,thenwecansimilarlyobtaintheresultsofthe(𝑎,1)-gamecoloringnumberof
theproductgraphoftreeandpath.
Keywords
TheCartesianProductofGraphs,TheDirectProductofGraphs,TheStrongProduct
ofGraphs,GameColoringNumber
Copyright
c
○2023byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.引言
假设𝐺=(𝑉,𝐸)是一个图.1991年,Bodlaender在[1]中提出了图 的博弈色数的概念.图𝐺的博
弈色数通过一个两个人的博弈定义.两个玩家,Alice和Bob,轮流对图𝐺的顶点使用同一个𝑘个颜
色的颜色集进行着色.在每个玩家的回合中,玩家从𝑉(𝐺)中选择一个未着色的顶点,并将此顶点
用𝑘个给定的颜色之一进行着色.Alice首先着 色,在每一回合 中,两个玩家对图𝐺的着色均为正常
染色.博弈直到𝐺的所有顶点都被着色或剩余的点没有可正常着色的方法.如果图𝐺中所有的顶点
都被给定的颜色染好,那么Alice赢,否则Bob赢.Alice的目标是在博弈结束以后,图𝐺的所有 点均
被着色;Bob的目标是在博弈结束以后,至少存在一个顶点没有被着色.博弈色数是使Alice有一个
赢的策略的最小颜色数,记作𝜒
𝑔
(𝐺).
在研究图博弈色数的过程中,Faigle, Kern,Kierstead和Trotter [2]考虑了标记博弈,并由Zhu
[3]正式的提出作为研究博弈 色数的工具.标记博弈的定义如下:两个玩家,Alice和Bob,轮流对图𝐺
未被标记的顶点进行标记,Alice首先进行标记.博弈 开始时,所有顶点都未标记.当图𝐺的所有 顶
点都被标记时,博弈结束.对于𝐺的每个顶点𝑣,用𝑏(𝑣)表示在𝑣标记之前标记的𝑣的邻点的个数.整
个博弈的分数为
𝑠= 1+max
𝑥∈𝑉(𝐺)
𝑏(𝑥).
Alice的目标是使整个博弈的分数尽可能的小;Bob的目标是使整个博弈的分数尽可能的大.博
弈染色数为最小的𝑠使得Alice有一个得分最多为𝑠的策略,记作𝑐𝑜𝑙
𝑔
(𝐺).
在2005年,Kierstead提出在[4]中提出了非对称版本的(𝑎,𝑏)-博弈染色数的相关概念.(𝑎,𝑏)-博
弈染色的规则除了要求每回合Alice和Bob分别染𝑎个顶点和𝑏个顶点以外,其余规则不变.(𝑎,𝑏)-博弈
染色数记为(𝑎,𝑏)-𝑐𝑜𝑙
𝑔
(𝐺).
DOI:10.12677/aam.2023.1241561505应用数学进展
苏俊义
对于一个图𝐺,设𝑂(𝐺)是图𝐺所有定向的集合.对于图𝐺的一个定向
⃗
𝐺以及
⃗
𝐺的一个点𝑥,
令𝑁
+
⃗
𝐺
(𝑥)为点𝑥的所有外邻点的集 合,令𝑑
+
⃗
𝐺
(𝑥)=|𝑁
+
⃗
𝐺
(𝑥)|为𝑥的出度.令∆
+
(
⃗
𝐺)=max
𝑣 ∈𝑉(𝐺)
𝑑
+
⃗
𝐺
(𝑣),
∆
*
(𝐺) = min
⃗
𝐺∈𝑂(𝐺)
∆
+
(
⃗
𝐺),∆(𝐺) = max
𝑣 ∈𝑉(𝐺)
𝑑
𝐺
(𝑣).
在2005年,Kierstead和Yang在[5]中给出了如下定理:
定理1[5]设𝑎是一个整数,如果图𝐺满足∆
*
(𝐺) = 𝑘≤𝑎,那么(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺)≤2𝑘+2.
下面我们分别介绍图𝐻
1
和𝐻
2
的笛卡尔积图、直积图和强积图的概念.
图𝐻
1
和𝐻
2
的笛卡尔积图𝐺=𝐻
1
2𝐻
2
的顶点集为𝑉(𝐺)=𝑉(𝐻
1
)×𝑉(𝐻
2
),边集为𝐸(𝐺) ,边
((𝑣,𝑥),(𝑤,𝑦)) ∈𝐸(𝐺)当且仅当:(1)𝑣= 𝑤且𝑥𝑦∈𝐸(𝐻
2
),或(2)𝑥= 𝑦且𝑣𝑤∈𝐸(𝐻
1
).
图𝐻
1
和𝐻
2
的直积图𝐺=𝐻
1
×𝐻
2
的顶点集为𝑉(𝐺)=𝑉(𝐻
1
)×𝑉(𝐻
2
),边集为𝐸(𝐺) ,边
((𝑣,𝑥),(𝑤,𝑦)) ∈𝐸(𝐺)当且仅当: 𝑣𝑤∈𝐸(𝐻
1
)且𝑥𝑦∈𝐸(𝐻
2
).
图𝐻
1
和𝐻
2
的强积图𝐺=𝐻
1
𝐻
2
的顶点集为𝑉(𝐺)=𝑉(𝐻
1
)×𝑉(𝐻
2
),边集为𝐸(𝐺) ,边
((𝑣,𝑥),(𝑤,𝑦))∈𝐸(𝐺) 当且仅当:(1) 𝑣=𝑤且𝑥𝑦∈𝐸(𝐻
2
) ,或(2) 𝑥=𝑦且𝑣𝑤∈𝐸(𝐻
1
) ,或(3)
𝑣𝑤∈𝐸(𝐻
1
)且𝑥𝑦∈𝐸(𝐻
2
).
通过笛卡尔积图、直积图和强积图的定义,我们可以发现图𝐻
1
和𝐻
2
的笛卡尔积图、直积图
和强积图的顶点集是相同的,并且图𝐻
1
和𝐻
2
的强积图的边集是图𝐻
1
和𝐻
2
的笛卡尔积图的边集
和直积图的边集不相交的并.
在[6]中作者给出了如下关于树和路的乘积图的博弈染色数的结果：
定理2[6]对于任意整数𝑎≥2,如果𝐺=𝑇2𝑃,其中𝑇是一棵树,𝑃是一条路,那么
(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺)≤6.
定理3[6]对于任意整数𝑎≥2,如果𝐺=𝑇×𝑃,其中𝑇是一棵树,𝑃是一条路,那么
(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺)≤6.
定理4[6]对于任意整数𝑎≥4,如果𝐺=𝑇𝑃,其中𝑇是一棵树,𝑃是一条路,那么
(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺)≤10.
本文主要研究的图是树和树的乘积图,利用定理1,我们给出树和树的三种乘积图的(𝑎,1)-博弈
染色数的上界.特别的,如果其中一棵树是一条 路,那么我们可以得到与文献[6]中关于树和路的乘
积图的博弈染色数相同的结果.
2.树和树乘积图的博弈染色数
令𝑇
1
和𝑇
2
是两棵树.令图𝐺是树𝑇
1
与树𝑇
2
的乘积图.我们对乘积图𝐺的边进行定向,给出
一个定向图
⃗
𝐺,得出图
⃗
𝐺的最大出度,再应用定理1得出图𝐺的(𝑎,1)-博弈染色数的上界.
首先我们分别取树𝑇
1
与树𝑇
2
的两个宽度优先顶点分层.令𝑢
𝑖,𝑗
和𝑣
𝑖,𝑗
分别表示树𝑇
1
与树𝑇
2
在宽度优先分层中的第𝑖层的第𝑗个元素.并称在第𝑖−1 层与点𝑢
𝑖,𝑗
邻接的点为点𝑢
𝑖,𝑗
的祖先,在
第𝑖+1层与点𝑢
𝑖,𝑗
邻接的点为点𝑢
𝑖,𝑗
的后代.由于𝑇
1
与𝑇
2
都是树,所以任意一个𝑇
1
或𝑇
2
中的点
DOI:10.12677/aam.2023.1241561506应用数学进展
苏俊义
最多只有一个祖先.由笛卡尔积图、直积图和强积图的定义我们知道,树𝑇
1
与树𝑇
2
的笛卡尔积图、
直积图和强积图的顶点集是相同的,为𝑉(𝐺) = 𝑉
1
∪𝑉
2
∪···∪𝑉
𝑖
∪···,其中
𝑉
𝑖
= {(𝑢
1,1
,𝑣
𝑖,1
),(𝑢
1,1
,𝑣
𝑖,2
),...,(𝑢
1,1
,𝑣
𝑖,𝑚
𝑖
),
(𝑢
2,1
,𝑣
𝑖,1
),(𝑢
2,1
,𝑣
𝑖,2
),...,(𝑢
2,1
,𝑣
𝑖,𝑚
𝑖
),(𝑢
2,2
,𝑣
𝑖,1
),(𝑢
2,2
,𝑣
𝑖,2
),...,(𝑢
2,2
,𝑣
𝑖,𝑚
𝑖
),···
.
.
.
(𝑢
𝑗,1
,𝑣
𝑖,1
),(𝑢
𝑗,1
,𝑣
𝑖,2
),...,(𝑢
𝑗,1
,𝑣
𝑖,𝑚
𝑖
),···}
我们称点(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)是𝑉
𝑝
的第𝑖层的元素.
对于乘积图𝐺的任意两个顶点(𝑢
𝑖
1
,𝑗
1
,𝑣
𝑖
2
,𝑗
2
) 和(𝑢
𝑖
3
,𝑗
3
,𝑣
𝑖
4
,𝑗
4
),我们 根据如下规则,将 乘积图𝐺
的顶点进行排序.
1.如果𝑖
1
<𝑖
3
,则(𝑢
𝑖
1
,𝑗
1
,𝑣
𝑖
2
,𝑗
2
) ≺
𝐿
(𝑢
𝑖
3
,𝑗
3
,𝑣
𝑖
4
,𝑗
4
);
2.如果𝑖
1
= 𝑖
3
且𝑖
2
<𝑖
4
,则(𝑢
𝑖
1
,𝑗
1
,𝑣
𝑖
2
,𝑗
2
) ≺
𝐿
(𝑢
𝑖
3
,𝑗
3
,𝑣
𝑖
4
,𝑗
4
);
3.如果𝑖
1
= 𝑖
3
,𝑖
2
= 𝑖
4
且𝑗
1
<𝑗
3
,则(𝑢
𝑖
1
,𝑗
1
,𝑣
𝑖
2
,𝑗
2
) ≺
𝐿
(𝑢
𝑖
3
,𝑗
3
,𝑣
𝑖
4
,𝑗
4
);
4.如果𝑖
1
= 𝑖
3
,𝑖
2
= 𝑖
4
,𝑗
1
= 𝑗
3
且𝑗
2
<𝑗
4
,则(𝑢
𝑖
1
,𝑗
1
,𝑣
𝑖
2
,𝑗
2
) ≺
𝐿
(𝑢
𝑖
3
,𝑗
3
,𝑣
𝑖
4
,𝑗
4
).
令满足上述规则的乘积图𝐺的顶点线性序为𝐿.根据顶点线性序𝐿我们给乘积图𝐺的边进行
定向,定向规则如下:
对任意一条边𝑒= (𝑢,𝑣) ∈𝐸(𝐺),边𝑒= (𝑢,𝑣) 的方向为从𝑢指向𝑣当且仅当𝑣<
𝐿
𝑢.
即从顶点线性序大的顶点指向顶点线性序小的顶点.
定理5令𝑇
1
和𝑇
2
是两棵树.对于任意整数𝑎≥2,如果图𝐺= 𝑇
1
2𝑇
2
,则(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤6.
证明首先我们对图𝐺中的边按照上述规 则进行定向.由集合𝑉
𝑖
和𝑉
𝑗
的定义和笛卡尔积图的
定义我们知道,如果|𝑖−𝑗|≥2,那么在顶点集𝑉
𝑖
和𝑉
𝑗
之间没有边相 连.所以根据我们上述定义的
边定向规则,任意一个顶点𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
) ∈𝑉(𝐺),我们有
1.对于同𝑉
𝑝
中与点𝑣关联的边
与在𝑉
𝑝
中𝑖−1层关联的边𝑒
1
=((𝑢
𝑖−1,𝑎
,𝑣
𝑝,𝑞
),(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
))是从点𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)指向点
(𝑢
𝑖−1,𝑎
,𝑣
𝑝,𝑞
);
与在𝑉
𝑝
中𝑖+1层关联的边𝑒=((𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
),(𝑢
𝑖+1,𝑏
,𝑣
𝑝,𝑞
))是从点(𝑢
𝑖+1,𝑏
,𝑣
𝑝,𝑞
)指向点𝑣=
(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
);
2.对于𝑉
𝑝−1
中与点𝑣关联的边
与在𝑉
𝑝−1
中关联的边𝑒
2
= ((𝑢
𝑖,𝑗
,𝑣
𝑝−1,𝑐
),(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
))是从点𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)指向点(𝑢
𝑖,𝑗
,𝑣
𝑝−1,𝑐
);
3.对于𝑉
𝑝+1
中与点𝑣关联的边
与在𝑉
𝑝+1
中关联的边𝑒= ((𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
),(𝑢
𝑖,𝑗
,𝑣
𝑝+1,𝑑
))是从点(𝑢
𝑖,𝑗
,𝑣
𝑝+1,𝑑
)指向点𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
).
由于𝑇
1
和𝑇
2
都是树,在𝑇
1
和𝑇
2
中的点都最多只有一个祖先,所以对任意一个顶点𝑣=
(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)∈𝑉(𝐺),最多在图𝐺中与𝑉
𝑝
的第𝑖−1 层的一个元素邻接,最多在图𝐺中与𝑉
𝑝−1
中的
一个元素邻接.所以任意一个顶点𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)∈𝑉(𝐺) 在
⃗
𝐺中的出度𝑑
+
(𝑣)≤2,所以由定理1
得(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤6.
DOI:10.12677/aam.2023.1241561507应用数学进展
苏俊义
定理6令𝑇
1
和𝑇
2
是两棵树, 设∆ = ∆(𝑇
2
) ≤∆(𝑇
1
).对于任意整数𝑎≥∆, 如果图𝐺= 𝑇
1
×𝑇
2
,
则(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤2∆+2.
证明首先我们对图𝐺中的边按照上述规 则进行定向.由集合𝑉
𝑖
和𝑉
𝑗
的定义和直积图的定义
我们知道,我们同样有如果|𝑖−𝑗|≥2,那么在顶点集𝑉
𝑖
和𝑉
𝑗
之间没有边相连,此外我们还可以得
到每一个𝑉
𝑖
在图𝐺=𝑇
1
×𝑇
2
上都是一个独立集.根据我们上述定义的边定向规则,任意一个顶点
𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
) ∈𝑉(𝐺),我们有
1.对于𝑉
𝑝−1
中与点𝑣关联的边
与在𝑉
𝑝−1
中𝑖−1 层关联的边𝑒
1
=((𝑢
𝑖−1,𝑎
,𝑣
𝑝−1,𝑏
),(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)) 是从点𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
) 指向点
(𝑢
𝑖−1,𝑎
,𝑣
𝑝−1,𝑏
);
与在𝑉
𝑝−1
中𝑖+ 1层关联的边𝑒=((𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
),(𝑢
𝑖+1,𝑐
,𝑣
𝑝−1,𝑑
))是从点(𝑢
𝑖+1,𝑐
,𝑣
𝑝−1,𝑑
)指向点
𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
);
2.对于𝑉
𝑝+1
中与点𝑣关联的边
与在𝑉
𝑝+1
中𝑖−1 层关联的边𝑒
2
=((𝑢
𝑖−1,𝑎
,𝑣
𝑝+1,𝑏
),(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)) 是从点𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
) 指向点
(𝑢
𝑖−1,𝑎
,𝑣
𝑝+1,𝑑
);
与在𝑉
𝑝+1
中𝑖+ 1层关联的边𝑒=((𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
),(𝑢
𝑖+1,𝑐
,𝑣
𝑝+1,𝑑
))是从点(𝑢
𝑖+1,𝑐
,𝑣
𝑝+1,𝑑
)指向点
𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
).
如果𝑝=1,则𝑉
𝑝−1
=∅,所以点𝑣与𝑉
𝑝−1
之间没有边.由于∆(𝑇
2
)=∆,且在树𝑇
1
上点𝑢
𝑖,𝑗
最多只有一个祖先𝑢
𝑖−1,𝑎
,所以点𝑣与在𝑉
𝑝+1
中𝑖−1层关联的边最多有1×∆ = ∆条;如果𝑝>1,
由于点𝑢
𝑖,𝑗
和点𝑣
𝑝,𝑞
分别在树𝑇
1
和𝑇
2
上都最多只有一个祖先,所以点𝑣与 在𝑉
𝑝−1
中𝑖−1 层关联
的边最多有1×1 = 1条,又由于∆(𝑇
2
) = ∆且点𝑣
𝑝,𝑞
在树𝑇
2
上有一个祖先,所以点𝑣与在𝑉
𝑝+1
中
𝑖−1 层关联的边最多有1×(∆−1) = ∆−1条.所以任意一个顶点𝑣= (𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
) ∈𝑉(𝐺)在
⃗
𝐺中
的出度𝑑
+
(𝑣) ≤∆,所以由定理1得(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤2∆+2.
定理7令𝑇
1
和𝑇
2
是两棵树,设∆=∆(𝑇
2
)≤∆(𝑇
1
).对于任意整数𝑎≥∆+2,如果图
𝐺= 𝑇
1
𝑇
2
,则(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤2∆+6.
证明令图𝐺
1
=𝑇
1
2𝑇
2
和𝐺
2
=𝑇
1
×𝑇
2
,由强积图的定义我们知道图𝐺=𝑇
1
𝑇
2
是
图𝐺
1
和𝐺
2
边不交的并.由定理5和定理6,我们知道图𝐺
1
和𝐺
2
分别有一个对任意顶点
𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)∈𝑉(𝐺)满足𝑑
+
(
⃗
𝐺
1
)≤2和𝑑
+
(
⃗
𝐺
2
)≤∆的定向.所以图𝐺=𝑇
1
𝑇
2
存在
一个对任意顶点𝑣=(𝑢
𝑖,𝑗
,𝑣
𝑝,𝑞
)∈𝑉(𝐺)满足𝑑
+
(
⃗
𝐺)≤∆ +2的定向.所以由定理1,我们有
(𝑎,1)-𝑐𝑜𝑙
𝑔
(𝐺) ≤2∆+6.
特殊地,如果树𝑇
2
是一条路𝑃,则∆(𝑇
2
)≤2,所以我们可以分别从定理[5,6,7]得到定理
[2,3,4] .
3.结语
关于图的博弈染色数有着非常丰富的结果,但关于乘积图的博弈染色数研究相对较少.本文通
过研究两棵树的乘积图,通过给出一个图的定向规则,得到了两棵树的乘积图(𝑎,1)-博弈染色数的
上界,推广 了文献[6]中的关于树和路的乘积图的(𝑎,1)-博弈染色数的结果.对于任意两个图 的乘积
DOI:10.12677/aam.2023.1241561508应用数学进展
苏俊义
图的博弈染色数的上界,仍然是值得进一步探讨的问题.
参考文献
[1]Bodlaender,H.L.(1991)OntheComplexityofSomeColoringGames.In:M¨ohring,R.H.,
Ed.,Graph-TheoreticConceptsinComputerScience.WG1990.LectureNotesinComputer
Science,Vol.484,Springer,Berlin,30-40.https://doi.org/10.1007/3-540-53832-129
[2]Faigle, U.,Kern,U., Kierstead,H. and Trotter,W.T. (1993) On the Game Chromatic Number
ofSomeClassesofGraphs.ArsCombinatoria,35,143-150.
[3]Zhu,X.(1999)TheGameColoringNumberofPlanarGraphs.JournalofCombinatorial
Theory,SeriesB,75,245-258.https://doi.org/10.1006/jctb.1998.1878
[4]Kierstead,H.A.(2005)AsymmetricGraphColoringGames.JournalofGraphTheory,48,
169-185.https://doi.org/10.1002/jgt.20049
[5]Kierstead,H.A.andYang,D.(2005)VeryAsymmetricMarkingGames.Order,22,93-107.
https://doi.org/10.1007/s11083-005-9012-y
[6]刘佳丽.树和路的乘积图的广义染色数及博弈染色数[J].应用数学进展,2022,11(1):318-325.
https://doi.org/10.12677/AAM.2022.111039
DOI:10.12677/aam.2023.1241561509应用数学进展

版权所有：汉斯出版社 (Hans Publishers) Copyright © 2023 Hans Publishers Inc. All rights reserved.