设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
A^
ê
Æ
?
Ð
,2022,11(1),318-325
PublishedOnlineJanuary2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.111039
ä
Ú
´
¦
È
ã
2
Â
/Ú
ê
9
Æ
‰
/Ú
ê
444
ZZZ
www
ú
ô
“
‰
Œ
Æ
ê
Æ
†
O
Ž
Å
‰
ÆÆ
§
ú
ô
7
u
Â
v
F
Ï
µ
2021
c
12
24
F
¶
¹
^
F
Ï
µ
2022
c
1
19
F
¶
u
Ù
F
Ï
µ
2022
c
1
26
F
Á
‡
©
?
Ø
{
ü
ã
ä
Ú
´
¦
È
ã
§
‰
Ñ
ä
Ú
´
¦
È
ã
˜
‡
‚
5S
§
0
§
2
Â
/Ú
ê
§
Ó
ž
‰
Ñ
ä
Ú
´
¦
È
ã
•
Œ
Ñ
Ý
•
›
•
˜
‡
~
ê
˜
‡
½
•
§
¿
d
d
0
ä
Ú
´
¦
È
ã
Æ
‰
/Ú
ê
"
'
…
c
¦
È
ã
§
Æ
‰
/Ú
ê
§
2
Â
/Ú
ê
TheGeneralizedColoringNumber
andGameColoringNumberof
ProductGraphofTree
andPath
JialiLiu
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Dec.24
th
,2021;accepted:Jan.19
th
,2022;published:Jan.26
th
,2022
©
Ù
Ú
^
:
4
Z
w
.
ä
Ú
´
¦
È
ã
2
Â
/Ú
ê
9
Æ
‰
/Ú
ê
[J].
A^
ê
Æ
?
Ð
,2022,11(1):318-325.
DOI:10.12677/aam.2022.111039
4
Z
w
Abstract
Thispaperconsiderstheproductgraphofsimplegraphtreeandpath,givesalinear
orderoftheproductgraphoftreeandpath,andintroducesthegeneralizedcoloring
numberoftheproductgraphoftreeandpath.Meanwhile,wegiveanorientationthat
themaximumout-degreeoftheproductgraphoftreeandpathisatmostaconstant
andintroducethegamecoloringnumberoftheproductgraphoftreeandpath.
Keywords
ProductGraph,GameColoringNumber,GeneralizedColoringNumber
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.
Ú
ó
3
2003
c
,
ã
2
Â
/Ú
ê
[1]
Ä
g
J
Ñ
,
3
1991
c
,Bodlaender
J
Ñ
ã
Æ
‰
/Ú
ê
[2]
V
g
.
a
q
,Kierstead
J
Ñ
(
a,b
)-
Æ
‰
/Ú
ê
[3]
V
g
.
¦
È
ã
˜
†
´
2
É
'
5
˜
a
ã
,
,
é
u
¦
È
ã
2
Â
/Ú
ê
±
9
Æ
‰
/Ú
ê
,
ï
Ä
,
©
ò
l
ã
2
Â
/Ú
ê
Ú
Æ
‰
/
Ú
ê
ù
ü
‡
ë
ê
Ñ
u
,
•
Ä
ä
Ú
´
¦
È
ã
2
Â
/Ú
ê
Ú
Æ
‰
/Ú
ê
.
©
•
Ä
¦
È
ã
•
±
e
n
«
:
(
k
È
,
†
È
,
r
È
.
Ä
k
·
‚
‰
Ñ
ù
n
«
¦
È
ã
½
Â
:
ã
A
Ú
ã
B
(
k
È
(
P
Š
A
2
B
)
d
:
8
V
(
A
)
×
V
(
B
)
|
¤
,
Ù
¥
,
Ø
Ó
:
(
v,x
)
,
(
w,y
)
∈
V
(
A
)
×
V
(
B
)
ƒ
…
=
÷
v
:(1)
v
=
w
…
xy
∈
E
(
B
),
½
(2)
x
=
y
…
vw
∈
E
(
A
) .
ã
A
Ú
ã
B
†
È
(
P
Š
A
×
B
)
d
:
8
V
(
A
)
×
V
(
B
)
|
¤
,
Ù
¥
,
Ø
Ó
:
(
v,x
)
,
(
w,y
)
∈
V
(
A
)
×
V
(
B
)
ƒ
…
=
÷
v
:
vw
∈
E
(
A
)
…
xy
∈
E
(
B
).
ã
A
Ú
ã
B
r
È
(
P
Š
A
B
)
d
:
8
V
(
A
)
×
V
(
B
)
|
¤
,
Ù
¥
,
Ø
Ó
:
(
v,x
)
,
(
w,y
)
∈
V
(
A
)
×
V
(
B
)
ƒ
…
=
÷
v
:(1)
v
=
w
…
xy
∈
E
(
B
),
½
(2)
x
=
y
…
vw
∈
E
(
A
),
½
(3)
vw
∈
E
(
A
)
…
xy
∈
E
(
B
).
d
(
k
È
,
†
È
,
r
È
½
Â
Œ
•
:
r
È
A
B
´
A
2
B
Ú
A
×
B
¿
.
DOI:10.12677/aam.2022.111039319
A^
ê
Æ
?
Ð
4
Z
w
e
5
,
·
‚
0
ã
2
Â
/Ú
ê
V
g
,
-
G
=(
V,E
)
´
˜
‡
ã
,
-
k
´
˜
‡
ê
.
-
Q
(G)
´
V
(
G
)
¤
k
‚
5S
8
Ü
,
L
∈
Q
(G) .
-
x
Ú
y
´
ã
G
ü
‡
º:
.
X
J
x
≺
L
y
¿
…
•
3
˜
^
y
−
x
•
Ý
•
õ
•
k
´
P
¦
é
´
þ
¤
k
S
:
z
÷
v
x
≺
L
z,
·
‚
¡
x
´
l
y
f
k
-
Œ
ˆ
.
d
,
X
J
é
´
P
þ
¤
k
S
:
z
÷
v
y
≺
L
z
,
·
‚
¡
x
´
l
yk
-
Œ
ˆ
.
-
R
k
(
G
L
§
y)
´
¤
k
l
yk
-
Œ
ˆ
º:
8
.
Q
k
(
G
L
§
y)
´
¤
k
l
y
f
k
-
Œ
ˆ
º:
8
,
R
k
[
G
L
§
y] =
R
k
(
G
L
§
y)
∪{
y
}
§
Q
k
[
G
L
§
y] =
Q
k
(
G
L
§
y)
∪{
y
}
.
½
Â
ã
G
k
-
coloringnumber
(
P
Š
col
k
(
G
) )
Ú
ã
G
weakk
-
coloringnumber
(
P
Š
wcol
k
(
G
))
•
col
k
(
G
)=min
L
∈
Q
(
G
)
max
v
∈
V
(
G
)
|
R
k
[
G
L
,y
]
|
Ú
wcol
k
(
G
)=min
L
∈
Q
(
G
)
max
v
∈
V
(
G
)
|
Q
k
[
G
L
,y
]
|
.
é
u
ã
Æ
‰
/Ú
,
3
1991
c
,Bodlaender
J
Ñ
ã
Æ
‰
/Ú
ê
V
g
.
a
q
,Kierstead
J
Ñ
ã
(
a,b
) -
Æ
‰
/Ú
ê
V
g
.
a
= 1
,b
=1
ž
,
ã
(
a,b
) -
Æ
‰
/Ú
ê
=
•
ã
Æ
‰
/
Ú
ê
,
Ï
d
©
Ì
‡
•
Ä
ä
Ú
´
¦
È
ã
š
é
¡
œ
¹
e
Æ
‰
/Ú
ê
=
(
a,
1) -
Æ
‰
/Ú
ê
.
e
5
·
‚
‰
Ñ
ã
Æ
‰
/Ú
ê
Ú
(
a,b
)-
Æ
‰
/Ú
ê
½
Â
.
ã
G
Æ
‰
/Ú
ê´
d
˜
‡
I
P
Æ
‰
½
Â
.
ã
G
I
P
Æ
‰
¥
,
å
Ð
¤
k
:Ñ
™
I
P
,Alice
Ú
Bob
Ó6
I
P
G
¥
™
I
P
º:
,
d
Alice
k
m
©
I
P
.
Ü
º:
I
P
Æ
‰
(
å
.
é
u
ã
G
z
˜
‡
º:
x
,
-
b
(
x
)
L
«
•
3
x
I
P
c
x
I
P
Ø
ê
.
Æ
‰
©
ê
½
Â
•
s
= 1+max
x
∈
V
(
G
)
b
(
x
)
.
Alice
8
I
´¦
©
ê
•
,
Bob
8
I
´¦
©
ê
•
Œ
.
Æ
‰
/Ú
ê
•
•
s
¦
Alice
k
˜
‡
ü
Ñ
¦
©
ê
•
õ
•
s
.
P
Š
col
g
(
G
).
ã
G
(
a,b
)-
Æ
‰
/Ú
ê
Æ
‰
9
©
ê
Ú
I
P
Æ
‰
˜
,
Ø
Ó
ƒ
?
3
u
z
˜
‡
I
P
£
Ü
¥
Alice
I
P
a
‡
:
,
Bob
I
P
b
‡
:
.(
a,b
) -
Æ
‰
/Ú
ê
•
•
s
¦
Alice
k
˜
‡
ü
Ñ
¦
©
ê
•
õ
•
s
.
P
Š
(
a,b
)-
col
g
(
G
).
é
u
˜
‡
ã
G
,
O
(
G
)
´
ã
G
¤
k
½
•
8
Ü
.
é
u
ã
G
˜
‡
½
•
~
G
±
9
~
G
˜
‡
:
x
,
-
N
+
~
G
(
x
)
P
Š
•
:
x
¤
k
Ø
8
Ü
,i.e.,
N
+
~
G
(
x
) =
{
y
:
x
→
y
}
.
-
d
+
~
G
(
x
)
•
x
Ñ
Ý
,i.e.,
d
+
~
G
(
x
) =
|
N
+
~
G
(
x
)
|
.
-
∆
+
~
G
= max
v
∈
V
d
+
~
G
(
v
),∆
∗
(
G
) = min
~
G
∈
O
(
G
)
∆
+
~
G
.
é
u
˜
‡
ã
G
,
~
G
´
ã
G
˜
‡
½
•
,
é
u
G
¥
z
‡
:
v
,
-
L
v
•
N
+
~
G
(
v
)
˜
‡
‚
5S
.
-
P
=
{
L
v
:
v
∈
V
(
G
)
}
,
X
J
v<
L
z
u
,
@
o
¡
z
é
'
u
`
k
v
.
X
J
v
∈
N
+
~
G
(
u
)
½
ö
•
3
˜
‡
:
z
¦
u,v
∈
N
+
~
G
(
z
)
…
z
é
'
u
`
k
v
,
@
o
¡
v
´
u
˜
‡
t
Ø
,
R
~
G
(
P
,U
)
P
Š
:
u
t
Ø
8
Ü
.
-
r
~
G
(
X
) =max
u
∈
V
(
G
)
|
R
~
G
(
X
,U
)
|
~
G
rank
½
Â
•
r
~
G
= min
P
|
r
~
G
(
X
)
|
.
DOI:10.12677/aam.2022.111039320
A^
ê
Æ
?
Ð
4
Z
w
Ú
n
1[4]
a
´
˜
‡
ê
,
X
J
ã
G
÷
v
∆
∗
(
G
) =
k
≤
a
,
@
o
(
a,
1)-
col
g
(
G
)
≤
2
k
+2 .
Ú
n
2[5]
X
J
~
G
´
˜
‡
∆
+
~
G
=
k>a
k
•
ã
,
-
r
~
G
(
P
)=
r
,
@
o
(
a,
1)-
col
g
(
G
)
≤
k
+
b
(1+
1
a
)
r
c
+2 .
2.
ä
Ú
´
¦
È
ã
2
Â
/Ú
ê
-
T
´
˜
†
ä
,
P
´
˜
^
´
.
é
u
ä
T
Ú
´
P
¦
È
ã
G
,
·
‚
Š
â
ä
T
¥
:
°
Ý
`
k
ü
S
±
9
´
P
¥
:
ü
S
,
‰
ã
G
:
?
1
ü
S
.
Š
â
¦
È
ã
A
:
9
ã
G
:
‚
5S
,
Ï
L
O
Ž
y
²
Ñ
Ø
Ó
¦
È
ã
2
Â
/Ú
ê
.
½
n
1
é
¤
k
ê
k>
0
X
J
ã
G
=
T
×
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
wcol
k
(
G
)
≤
k
2
+
k
+1.
col
k
(
G
)
≤
k
+2 .
y
²
é
u
ä
T
,
·
‚
‰
§
:
?
1
°
Ý
`
k
ü
S
,
ä
T
:
‚
5S
P
Š
σ
∈
Q
(
T
) .
b
x
0
,
1
´ä
ä
Š
,
x
0
,
1
•
°
Ý
`
k
©
1
0
,
-
1
i
1
j
‡
:
P
•
x
i,j
.
é
u
´
P
,
·
‚
‰
§
:
(
y
1
,y
2
,...,y
m
,...
)
?
1
˜
‡
ü
S
P
Š
τ
,
y
i
<
τ
y
j
…
=
i<j
.
@
o
é
u
ã
G
=
T
P
,
:
8
•
V
(
G
)=((
x
0
,
1
,y
1
)
,
(
x
0
,
1
,y
2
)
,...,
(
x
0
,
1
,y
m
)
,...,
(
x
1
,
1
,y
1
)
,
(
x
1
,
1
,y
2
)
,...,
(
x
1
,
1
,y
m
)
,...,
(
x
i,
1
,y
1
)
,
(
x
i,
1
,y
2
)
,...,
(
x
i,
1
,y
m
)
,...
) .
é
u
ã
G
:
?
1
ü
S
,
-
L
•
ã
G
º:
U
ì
±
e
5
K
ü
‚
5S
.
é
ã
G
?
¿
ü
‡
:
(
x
i,j
,y
m
),(
x
i
0
,j
0
,y
m
0
):
1.
X
J
i
6
=
i
0
,
@
o
(
x
i,j
,y
m
)
≺
L
(
x
i
0
,j
0
,y
m
0
)
…
=
i
≤
i
0
.
2.
X
J
i
=
i
0
,
j
6
=
j
0
,
@
o
(
x
i,j
,y
m
)
≺
L
(
x
i
0
,j
0
,y
m
0
)
…
=
j
≤
j
0
.
3.
X
J
i
=
i
0
…
j
=
j
0
,
@
o
(
x
i,j
,y
m
)
≺
L
(
x
i
0
,j
0
,y
m
0
)
…
=
m
≤
m
0
.
é
u
ã
G
:
?
1
©
:
-
(
x
0
,
1
,y
1
) , (
x
0
,
1
,y
2
) ,..., (
x
0
,
1
,y
m
) ,...
•
1
˜
:
,
-
(
x
1
,
1
,y
1
) ,
(
x
1
,
1
,y
2
),...,(
x
1
,
1
,y
m
),...
•
1
:
,...
§
-
(
x
i,
1
,y
1
),(
x
i,
1
,y
2
),...,(
x
i,
1
,y
m
)
,...
•
1
i
:
.
d
ã
G
©
±
9
f
k
-
Œ
ˆ
½
Â
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
é
u
?
¿˜
‡
:
v
∈
G
(
:
v
•
1
l
:
)
5
`
,
l
v
f
k
-
Œ
ˆ
:
y
0
Œ
U
á
3
1
p
(
l
−
k
≤
p
≤
l,l
≥
k
)
,
…
y
0
≺
L
v
,
du
G
¥
:
3
Ó
˜
v
k
>
,
Ï
d
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
–
õ
•
b
k
2
c
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
2
d
k
2
e
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
2
–
õ
•
1+2
b
k
2
c
,
(
k
≥
2) ,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
3
–
õ
•
2
d
k
2
e
,
(
k
≥
3) ,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
4
–
õ
•
1+2
b
k
2
c
,
(
k
≥
4) ,
,...,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
i
–
õ
•
2
d
k
2
e
,
(
k
≥
i
)
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
i
−
1
–
õ
•
1+2
b
k
2
c
,
(
k
≥
i
+1),
DOI:10.12677/aam.2022.111039321
A^
ê
Æ
?
Ð
4
Z
w
Ï
d
,
·
‚
k
k
•
ó
êž
,
wcol
k
(
G
)
≤b
k
2
c
+(2
d
k
2
e
+1+2
b
k
2
c
)
k
2
+1.
k
•
Û
êž
,
wcol
k
(
G
)
≤
b
k
2
c
+(2
d
k
2
e
+1+2
b
k
2
c
)
k
−
1
2
+2
d
k
2
c
+1.
n
:
wcol
k
(
G
)
≤
k
2
+
k
+1.
d
ã
G
©
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
,
é
u
?
¿˜
‡
:
v
∈
G
5
`
,
k
≥
2
ž
,
l
vk
-
Œ
ˆ
:
y
0
•
U
á
3
:
v
¤
3
þ
(
Ø
”
•
1
l
)
9
:
v
þ
˜
(
Ø
”
•
1
l
−
1
),
…
y
0
≺
L
v
,
du
G
¥
:
3
Ó
˜
v
k
>
,
Ï
dl
v k
-
Œ
ˆ
:
3
1
l
–
õ
•
b
k
2
c
,
l
vk
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
d
k
+2
2
e
,
Ï
d
,
·
‚
k
col
k
(
G
)
≤
k
+2.
½
n
2
é
¤
k
ê
k>
0
X
J
ã
G
=
T
2
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
wcol
k
(
G
)
≤
k
2
+
k
+1.0
<k
≤
2
ž
§
col
k
(
G
)
≤
3;
k>
2
ž
§
col
k
(
G
)
≤
2
k
−
1 .
y
²
é
u
ä
T
,
·
‚
‰
§
:
?
1
°
Ý
`
k
ü
S
,
ä
T
:
‚
5S
P
Š
σ
∈
Q
(
T
) .
b
x
0
,
1
´ä
ä
Š
,
x
0
,
1
•
°
Ý
`
k
©
1
0
,
-
1
i
1
j
‡
:
P
•
x
i,j
.
é
u
´
P
,
·
‚
‰
§
:
(
y
1
,y
2
,...,y
m
,...
)
?
1
˜
‡
ü
S
P
Š
τ
,
y
i
<
τ
y
j
…
=
i<j
.
@
o
é
u
ã
G
=
T
P
,
:
8
•
V
(
G
)=((
x
0
,
1
,y
1
)
,
(
x
0
,
1
,y
2
)
,...,
(
x
0
,
1
,y
m
)
,...,
(
x
1
,
1
,y
1
)
,
(
x
1
,
1
,y
2
)
,...,
(
x
1
,
1
,y
m
)
,...,
(
x
i,
1
,y
1
)
,
(
x
i,
1
,y
2
)
,...,
(
x
i,
1
,y
m
)
,...
) .
du
ü
‡
ã
T
P
Ú
T
×
P
:
8
ƒ
Ó
,
·
‚
é
ã
T
×
P
¥
:
ü
S
Ú
©
æ
^
½
n
1
¥
•
{
,
•
;
•
-
E
,
ù
p
†
¦
^
½
n
1
¥
:
ü
S
Ú
©
.
d
ã
G
©
±
9
f
k
-
Œ
ˆ
½
Â
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
é
u
?
¿˜
‡
:
v
∈
G
(
:
v
•
1
l
:
)
5
`
,
l
v
f
k
-
Œ
ˆ
:
y
0
Œ
U
á
3
1
p
(
l
−
k
≤
p
≤
l,l
≥
k
)
,
…
y
0
≺
L
v
,
Ï
d
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
–
õ
•
k
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
1+2(
k
−
1) ,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
2
–
õ
•
1+2(
k
−
2)
,
(
k
≥
2) ,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
3
–
õ
•
1+2(
k
−
3)
,
(
k
≥
3) ,
,...,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
i
–
õ
•
1+2(
k
−
i
)
,
(
k
≥
i
) ,
Ï
d
,
·
‚
k
wcol
k
(
G
)
≤
k
+1 +2(
k
−
1)+1 +2(
k
−
2)+
...
+ 1+ 2(
k
−
k
)+ 1.
n
:
wcol
k
(
G
)
≤
k
2
+
k
+1.
d
ã
G
©
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
,
é
u
?
¿˜
‡
:
v
∈
G
5
`
,
k
≥
2
ž
,
l
vk
-
Œ
ˆ
:
y
0
•
U
á
3
:
v
¤
3
þ
(
Ø
”
•
1
l
)
9
:
v
þ
˜
(
Ø
”
•
1
l
−
1
),
…
y
0
≺
L
v
,
d
½
Â
Œ
•
G
¥
:
3
Ó
˜
k
>
,
…
é
u
?
¿˜
:
(
x
i,j
,y
m
)
–
õ
•
k
ü
‡
Ø
•
(
x
i,j
,y
m
−
1
) ,(
x
i,j
,y
m
+1
) ,
Ï
d
k>
2
ž
,
l
v k
-
Œ
ˆ
:
3
1
l
–
õ
•
k
−
2,
l
vk
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
k
,
Ï
d
,
·
‚
k
0
<k
≤
2
ž
§
col
k
(
G
)
≤
3;
k>
2
ž
§
col
k
(
G
)
≤
2
k
−
1 .
½
n
3
é
¤
k
ê
k>
0
X
J
ã
G
=
T
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
wcol
k
(
G
)
≤
2
k
2
+
k
+1.
col
k
(
G
)
≤
2
k
+3 .
y
²
é
u
ä
T
,
·
‚
‰
§
:
?
1
°
Ý
`
k
ü
S
,
ä
T
:
‚
5S
P
Š
σ
∈
Q
(
T
) .
b
x
0
,
1
´ä
ä
Š
§
x
0
,
1
•
°
Ý
`
k
©
1
0
,
-
1
i
1
j
‡
:
P
•
x
i,j
.
é
u
´
P
,
·
‚
DOI:10.12677/aam.2022.111039322
A^
ê
Æ
?
Ð
4
Z
w
‰
§
:
(
y
1
,y
2
,...,y
m
,...
)
?
1
˜
‡
ü
S
P
Š
τ
,
y
i
<
τ
y
j
…
=
i<j
.
@
o
é
u
ã
G
=
T
P
,
:
8
•
V
(
G
)=((
x
0
,
1
,y
1
)
,
(
x
0
,
1
,y
2
)
,...,
(
x
0
,
1
,y
m
)
,...,
(
x
1
,
1
,y
1
)
,
(
x
1
,
1
,y
2
)
,...,
(
x
1
,
1
,y
m
)
,...,
(
x
i,
1
,y
1
)
,
(
x
i,
1
,y
2
)
,...,
(
x
i,
1
,y
m
)
,...
) .
du
ü
‡
ã
T
P
Ú
T
×
P
:
8
ƒ
Ó
,
·
‚
é
ã
T
×
P
¥
:
ü
S
Ú
©
æ
^
½
n
1
¥
•{
,
•
;
•
-
E
,
ù
p
†
¦
^
½
n
1
¥
:
ü
S
Ú
©
.
d
ã
G
©
±
9
f
k
-
Œ
ˆ
½
Â
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
é
u
?
¿˜
‡
:
v
∈
G
(
:
v
•
1
l
:
)
5
`
,
l
v
f
k
-
Œ
ˆ
:
y
0
Œ
U
á
3
1
p
(
l
−
k
≤
p
≤
l,l
≥
k
)
,
…
y
0
≺
L
v
,
Ï
d
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
–
õ
•
k
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
1+2
k
,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
2
–
õ
•
1+2
k,
(
k
≥
2) ,
,...,
l
v
f
k
-
Œ
ˆ
:
3
1
l
−
i
–
õ
•
1+2
k,
(
k
≥
i
) ,
Ï
d
,
·
‚
k
wcol
k
(
G
)
≤
k
+(1+2
k
)
k
+1 .
n
:
wcol
k
(
G
)
≤
2
k
2
+
k
+1.
d
ã
G
©
Œ
•
µ
|
i
−
j
|≥
2
ž
,
1
i
:
†
1
j
:
v
k
>
ƒ
ë
,
Ï
d
,
é
u
?
¿˜
‡
:
v
∈
G
5
`
,
k
≥
2
ž
,
l
vk
-
Œ
ˆ
:
y
0
•
U
á
3
:
v
¤
3
þ
(
Ø
”
•
1
l
)
9
:
v
þ
˜
(
Ø
”
•
1
l
−
1
),
…
y
0
≺
L
v
,
d
½
Â
Œ
•
G
¥
:
3
Ó
˜
k
>
,
…
é
u
?
¿˜
:
(
x
i,j
,y
m
)
–
õ
•
k
ü
‡
Ø
•
(
x
i,j
,y
m
−
1
) ,(
x
i,j
,y
m
+1
) ,
Ï
d
k>
2
ž
,
l
v k
-
Œ
ˆ
:
3
1
l
–
õ
•
k
,
l
vk
-
Œ
ˆ
:
3
1
l
−
1
–
õ
•
k
+2 ,
Ï
d
,
·
‚
k
col
k
(
G
)
≤
2
k
+3 .
3.
ä
Ú
´
¦
È
ã
Æ
‰
/Ú
ê
-
T
´
˜
†
ä
,
P
´
˜
^
´
.
é
u
ä
T
Ú
´
P
¦
È
ã
G
Æ
‰
/Ú
ê
,
·
‚
Ï
L
‰
ã
G
˜
‡
Ü
·
½
•
,
¦
ã
G
•
Œ
Ñ
Ý
•
˜
‡
~
ê
,
2
(
Ü
Ú
n
1
Ñ
ã
G
(
a,
1) -
Æ
‰
/Ú
ê
.
½
n
4
é
u
?
¿
ê
a
≥
2
X
J
G
=
T
×
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
(
a,
1)-
col
g
(
G
)
≤
6.
y
²
é
u
ã
G
:
,
·
‚
†
æ
^
½
n
1
ü
S
Ú
©
.
e
5
·
‚
é
ã
G
>
?
1
½
•
,
d
T
×
P
½
±
9
·
‚
é
T
×
P
¥
:
©
´
•
,
ã
T
×
P
v
k
Ó
˜
>
.
é
u
ƒ
>
©
•
ü
«
œ
¹
µ
1.
e
= ((
x
i
−
1
,a
,y
m
−
1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
−
1
).
2.
e
= ((
x
i
−
1
,a
,y
m
+1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
+1
).
Ï
d
,
é
?
¿˜
‡
:
(
x
i,j
,y
m
)
Ñ
k
d
+
G
((
x
i,j
,y
m
))
≤
2
Š
â
Ú
n
1
Œ
(
a,
1)-
col
g
(
G
)
≤
6.
½
n
5
é
u
?
¿
ê
a
≥
2
X
J
G
=
T
2
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
(
a,
1)-
col
g
(
G
)
≤
6.
y
²
é
u
ã
G
:
,
·
‚
†
æ
^
½
n
1
ü
S
Ú
©
.
e
5
·
‚
é
ã
G
>
?
1
½
•
,
é
u
Ó
˜
>
e
= ((
x
i,j
,y
m
−
1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
DOI:10.12677/aam.2022.111039323
A^
ê
Æ
?
Ð
4
Z
w
(
x
i,j
,y
m
−
1
) .
é
u
ƒ
>
e
= ((
x
i
−
1
,a
,y
m
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
) .
Ï
d
,
é
?
¿˜
‡
:
(
x
i,j
,y
m
)
Ñ
k
d
+
G
((
x
i,j
,y
m
))
≤
2
Š
â
Ú
n
1
Œ
(
a,
1)-
col
g
(
G
)
≤
6.
½
n
6
é
u
?
¿
ê
a
≥
4,
X
J
G
=
T
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
@
o
(
a,
1)-
col
g
(
G
)
≤
10.
y
²
é
u
ã
G
:
,
·
‚
†
æ
^
½
n
1
ü
S
Ú
©
.
e
5
·
‚
é
ã
G
>
?
1
½
•
,
é
u
Ó
˜
>
e
= ((
x
i,j
,y
m
−
1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i,j
,y
m
−
1
).
é
u
ƒ
>
©
•
n
«
œ
¹
µ
1.
e
= ((
x
i
−
1
,a
,y
m
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
).
2.
e
= ((
x
i
−
1
,a
,y
m
−
1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
−
1
).
3.
e
= ((
x
i
−
1
,a
,y
m
+1
)
,
(
x
i,j
,y
m
))
•
•
l
(
x
i,j
,y
m
)
(
x
i
−
1
,a
,y
m
+1
).
Ï
d
,
é
?
¿˜
‡
:
(
x
i,j
,y
m
)
Ñ
k
d
+
G
((
x
i,j
,y
m
))
≤
4
Š
â
Ú
n
1
Œ
(
a,
1)-
col
g
(
G
)
≤
10.
é
u
a<
4
ž
,
(
Ü
½
n
1
½
•
,
Œ
±
±
e
í
Ø
µ
í
Ø
1
é
u
?
¿
ê
a<
4
X
J
G
=
T
P
,
Ù
¥
T
´
˜
†
ä
,
P
´
˜
^
´
,
-
r
~
G
(
P
) =
r
,
@
o
(
a,
1)
−
col
g
(
G
)
≤
4+
b
(1+
1
a
)
r
c
+2 .
y
²
d
½
n
3
Œ
•
é
?
¿˜
‡
:
(
x
i,j
,y
m
),
d
+
G
((
x
i,j
,y
m
))
≤
4,
Š
â
Ú
n
2
Œ
(
a,
1)
−
col
g
(
G
)
≤
4+
b
(1+
1
a
)
r
c
+2 .
4.
(
Š
©
‰
Ñ
ä
Ú
´
¦
È
ã
2
Â
/Ú
ê
þ
.
±
9
(
a,b
) -
Æ
‰
/Ú
ê
þ
.
.
¿
3
y
²
L
§
¥
‰
Ñ
ä
Ú
´
¦
È
ã
˜
‡
‚
5S
±
9
•
Œ
Ñ
Ý
•
›
•
˜
‡
~
ê
½
•
,
3
ï
Ä
,
ã
ë
ê
ž
,
I
‡
^
ã
•
Œ
Ñ
Ý
.
T
½
•
J
ø
ï
Ä
g
´
.
3
ã
Ø
¥
,
¦
È
ã
2
Â
/Ú
ê
Ú
Æ
‰
/Ú
ê
ï
Ä
,
Ø
Óã
¦
È
ã
2
Â
/Ú
ê
9
Æ
‰
/Ú
ê
Ñ
´
Š
?
˜
Ú
&?
¯
K
.
©
‰
Ñ
ä
Ú
´
¦
È
ã
±
9
¦
‚
2
Â
/Ú
ê
,
?
Ø
¦
È
ã
Æ
‰
/Ú
ê
,
@
o
é
u
?
¿
ü
‡
ã
¦
È
ã
2
Â
/Ú
ê´
Ä
k
˜
‡
‚
5
þ
.
Q
,
ù
•
´
Š
?
˜
Ú
&?
¯
K
.
ë
•
©
z
[1]Kierstead,H.A. and Yang D. (2003) Orderings on Graphs and Game Coloring Number.
Order
,
20
,255-264.https://doi.org/10.1023/B:ORDE.0000026489.93166.cb
[2]Bodlaender,H.L.(1991)OntheComplexityofSomeColoringGames.In:M¨ohring,R.H.,
Eds.,
Graph-TheoreticConceptsinComputerScience.WG1990.LectureNotesinComputer
Science
,Springer,Berlin,30-40.https://doi.org/10.1007/3-540-53832-129
[3]Kierstead,H.A.(2005)AsymmetricGraphColoringGames.
JournalofGraphTheory
,
48
,
169-185.https://doi.org/10.1002/jgt.20049
DOI:10.12677/aam.2022.111039324
A^
ê
Æ
?
Ð
4
Z
w
[4]Kierstead,H.A.andYang,D.(2005)VeryAsymmetricMarkingGames.
Order
,
22
,93-107.
https://doi.org/10.1007/s11083-005-9012-y
[5]Yang,D.andZhu,X.(2008)ActivationStrategyforAsymmetricMarkingGames.
European
JournalofCombinatorics
,
29
,1123-1132.https://doi.org/10.1016/j.ejc.2007.07.004
DOI:10.12677/aam.2022.111039325
A^
ê
Æ
?
Ð