그래프 컬러링 게임

그래프 컬러링 게임은 그래프 이론과 관련된 수학 게임이다.색칠 게임 문제는 잘 알려진 그래프 색칠 문제의 게임 이론적 버전에서 비롯되었다.컬러링 게임에서, 두 명의 플레이어는 우리가 고려하는 게임에 따라 특정한 규칙을 따라 그래프의 컬러링을 구성하기 위해 주어진 색상 세트를 사용한다.한 플레이어는 그래프의 색상을 성공적으로 완성하려고 하는데, 다른 플레이어는 그래프를 달성하지 못하게 하려고 한다.

정점 염색 게임

정점 염색 게임은 1981년 브람스에^[1] 의해 도입되었고 보들렌더에 의해 10년 후에 재발견되었다.^[2]그 규칙은 다음과 같다.

1. 앨리스와 밥은 그래프 G의 꼭지점에 색을 칠한다.
2. 앨리스와 밥이 교대로 돌아가면서, 미색 정점을 적절히 색칠한다(표준 버전에서는 앨리스가 시작된다).
3. 정점 v가 제대로 색칠할 수 없는 경우(어떤 색이든 v가 색칠한 인접 항목이 있음), 밥이 이긴다.
4. 그래프가 완전히 색칠되면 앨리스가 승리한다.

The game chromatic number of a graph ${\displaystyle G}$, denoted by ${\displaystyle \chi _{g}(G)}$, is the minimum number of colors needed for Alice to win the vertex coloring game on ${\displaystyle G}$. Trivially, for every graph ${\displaystyle G}$, we have ${\displaystyle \chi (G)\le {\chi }_g(G)\le \mathrm{\Delta }(G)+1}$${\$$displaystyle$ ^[3]$\$$chi$ ($G)\leq \chi _{g}(G)\leq$ $\$$Delta$ $(G)+1$ 여기서 $($는 $(\displaystyle G)$와 $G)$의 색수(chromatic number of G)이다$.$

다른 개념과의 관계

유채색.Acyclic 색도 $번호{\displaystyle }$ k가 ${\displaystyle k}$인 모든 $그래프{\displaystyle }$ G ${\displaystyle G}$에는 ${\displaystyle \mathrm{has}}$ g (${\displaystyle {}_{}}$G${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle k}$(${\displaystyle k}$+ ${\displaystyle 1}$) ${\displaystyle \chi _{g}(G)\leq k(k+1$)가 있다$$$.$^[4]

마킹 게임.For every graph ${\displaystyle G}$, ${\displaystyle \chi _{g}(G)\leq col_{g}(G)}$, where ${\displaystyle col_{g}(G)}$ is the game coloring number of ${\displaystyle G}$. Almost every known upper bound for the game chromatic number of graphs are obtained from bounds on게임 컬러링 번호

가장자리의 주기 제한그래프 $G{\displaystyle }$ ${\displaystyle G}$의 모든 에지가 $최대{\displaystyle }$ c ${\$${\displaystyle \mathrm{displaystyle}}$ $c}$ 사이클에$$ 속하면$$ ${\displaystyle {\chi }_{}}$ g${\displaystyle {}_{}}$( G${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle 4}$+ ${\displaystyle c}$ ${\displaystyle \chi _{g}(G)\leq 4+c}$^[5].

그래프 클래스

For a class ${\displaystyle {\mathcal {C}}}$ of graphs, we denote by ${\displaystyle \chi _{g}({\mathcal {C}})}$ the smallest integer ${\displaystyle k}$ such that every graph ${\displaystyle G}$ of ${\displaystyle {\mathcal {C}}}$ has ${\displaystyle \chi _{g}(G$$)\$${\displaystyle leq\mathcal{}}$ $k$ 즉, $\chi {\displaystyle {}_{}}$ ${\displaystyle g_{}}$( C${\displaystyle }$) ${\displaystyle \chi _{g}({\mathcal{C})$은 이$$ 클래스의 게임 색도 수에 대한 정확한 상한이다.이 값은 몇 가지 표준 그래프 클래스에 대해 알려져 있으며 일부 다른 클래스에는 한계가 있다.

• 숲: $\chi {\displaystyle {}_{}}$ ${\displaystyle g_{}}$(${\displaystyle F}$)${\displaystyle }$= ${\displaystyle 4}$ ${\displaystyle \chi _{g}({\mathcal{F})=4$^[6] 간단한 기준은 3도 정점 없는 숲의 게임 색수를 결정하는 것으로 알려져 있다.^[7]최고도 3도의 숲에서도 3도의 정점을 가진 숲의 게임 색채 수를 결정하기는 어려워 보인다.
• 선인장: $\chi {\displaystyle {}_{}}$ ${\displaystyle g_{}}$( ${\displaystyle C}$)${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle \chi _{g}({\mathcal{C})=5$^[8] .
• Outerplanar 그래프: ${\displaystyle 6_{}}$: ≤ ${\displaystyle \mathrm{g}}$ ${\displaystyle {}_{}O}$) ${\displaystyle \le }$ 7 ${\displaystyle 6\leq \chi _{g}({\mathcal {O}})\leq$ 7$}$^[9].
• 평면 그래프: 7${\displaystyle }7{\displaystyle \mathrm{}}$ ${\displaystyle \chi \mathcal{}}$ ${\displaystyle g_{}}$( P${\displaystyle }$) ${\displaystyle \le }$ ${\displaystyle 17}$ ${\displaystyle 7\leq \chi _{g}({\mathcal {P})\leq 17}$^[10].
• 주어진 허리 둘레Planar 그래프:χ g(P4)≤ 13{\displaystyle \chi_{g}({{P}}_{4}\mathcal)\leq 13},[11]χ g(P5)≤ 8{\displaystyle \chi_{g}({{P}}_{5}\mathcal)\leq 8},χ g(P6)≤ 6{\displaystyle \chi_{g}({{P}}_{6}\mathcal)\leq 6},χ g(28)≤ 5{\displaystyl.e\c$안녕 _{g}({\mathcal {P}_{8}}\leq 5}$^[12].
• Toroidal 그리드: ${\displaystyle {}_{}}$ ${\displaystyle g_{}}$ (T ${\displaystyle G}$)${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle \chi _{g}({\mathcal{T}G}}=5$^[13] .
• 부분 k-tree: ${\displaystyle {\chi }_{}}$ g (${\displaystyle {}_{}{T}_{}}$ k${\displaystyle {}_{}}$) ${\displaystyle \le }$ ${\displaystyle 3}$ ${\displaystyle \mathrm{k}}$+ 2 ${\displaystyle \chi _{g}({\mathcal{T}_{k})\leq 3k+2$}$$^[14].
• 구간 그래프: $2{\displaystyle \mathrm{}}$Ω ^[15]${\displaystyle {}_{}}$ ${\displaystyle g_{}}$(${\displaystyle I\mathcal{}}$ ${\displaystyle )}$≤ ${\displaystyle 3}$ ${\displaystyle \mathrm{\Omega }}$- 2 ${\displaystyle 2\omega \leq \chi _{g}({\mathcal{I})\leq 3\omega -2$ 여기서 $\Omega {\displaystyle }$ ${\displaysty \omega }$는 가장 큰 클라이크의 크기 그래프용이다$$.

데카르트 제품.The game chromatic number of the cartesian product ${\displaystyle G\square H}$ is not bounded by a function of ${\displaystyle \chi _{g}(G)}$ and ${\displaystyle \chi _{g}(H)}$. In particular, the game chromatic number of any complete bipartite graph ${\displaystyle K_{n,n}}$ is는 3과 같으나 임의 $n{\displaystyle }$,$$에 대한$$ ${\displaystyle {\chi }_{}}$ g${\displaystyle {}_{}}$(${\displaystyle {\mathrm{Kn}}_{}}$, n ${\displaystyle {}_{}}$ ${\displaystyle K_{}}$ ${\displaystyle {}_{}}$, m${\displaystyle {}_{}}$) ${\$$displaystyle$ $\chi _{g}(K_{n,n$},n$}\제곱 K_{m$$,m$$}}}}}$에 대한 상한은 없다$.$^[16]

• 단 하나의 가장자리:^[16]

${\displaystyle {\begin{aligned}\chi _{g}(K_{2}\square P_{k})&={\begin{cases}2&k=1\\3&k=2,3\\4&k\geq 4\end{cases}}\\\chi _{g}(K_{2}\square C_{k})&=4&&k\geq 3\\\chi _{g}(K_{2}\square K_{k})&=k+1\end{aligned}}}$

• 별의 경우:^[17]

${\displaystyle {\begin{aligned}\chi _{g}(S_{m}\square P_{k})&={\begin{cases}2&k=1\\3&k=2\\4&k\geq 3\end{cases}}\\\chi _{g}(S_{m}\square C_{k})&=4&&k\geq 3\end{aligned}}}$

• 나무: $\chi {\displaystyle {}_{}}$ ${\displaystyle g_{}}$(${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {T\mathrm{}}_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle \le }$ ${\displaystyle 12.}$${\displaystyle \chi _{g}(T_{1}\제곱 T_{2})\leq 12.$$}$
• 휠: $\chi {\displaystyle {}_{}}$ ${\displaystyle g_{}}$( P ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle W_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle \chi _{g}(P_{2}\square W_{n})=5}($$n{\displaystyle }$만일$$ n${\displaystyle \mathrm{\{}}$9. {\$displaystyle n\geq 9.}$
• 완전한 초당적 그래프: ${\displaystyle {\chi }_{}}$ g${\displaystyle {}_{}}$( P ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ K ${\displaystyle m_{}}$, ${\displaystyle n_{}}$)${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle \chi _{g}(P_{2}\square K_{m,n}=5}$인 경우${\displaystyle ,}$ m, ${\displaystyle n\mathrm{}\ge }$ 5. ${\displaystym m,n\geq$ 5$.}$

문제 열기

이 질문들은 아직 이 날짜까지 열려 있다.

엣지 컬러링 게임

람, 슈, 주 등이 선보인 엣지컬링 게임은 앨리스와 밥이 정점컬링 대신 적절한 엣지컬러를 구성한다는 점을 제외하면 정점컬링 게임과 비슷하다.^[19]그 규칙은 다음과 같다.

1. 앨리스와 밥은 그래프 G의 가장자리를 색상으로 칠하고 있다.
2. 앨리스와 밥이 번갈아 가며 제대로 무채색(표준 버전에서는 앨리스가 시작된다.
3. 엣지 e가 제대로 색칠할 수 없는 경우(어떤 색이든 e가 색칠된 엣지에 인접해 있음), 밥이 승리한다.
4. 그래프가 완전히 가장자리 색이면 앨리스가 이긴다.

이 게임은 선 그래프에서 정점 컬러링 게임의 특정 사례로 볼 수 있지만, 주로 과학 문헌에서 뚜렷한 게임으로 간주되고 있다.$\chi {\displaystyle {}_{}^{}}$ ${\displaystyle g_{}^{}}$ ${\displaystyle {}_{}^{}}$($$${\displaystyle G}$) ${\displaystyle \chi '_{g}(G$로 표시된 그래프 G ${\displaystyle G$$\}$의 게임 색지수는 앨리스가 $G{\displaystyle }$ ${\$displaystyle G}에서 이 게임을 이기는데 필요한 최소 색상 수입니다.

일반사례

For every graph G, ${\displaystyle \chi '(G)\leq \chi '_{g}(G)\leq 2\Delta (G)-1}$. There are graphs reaching these bounds but all the graphs we know reaching this upper bound have small maximum degree.^[19]의 큰 ${\displaystyle 값}$인$\Delta {\displaystyle \mathrm{}(}$ $$(G ) > .Δ ) {\$displaystyle \chi$'$_$${g$}(G$)>1.008\$$Delta(G)}$을(를) 가진 그래프가 존재한다$.$^[20]

추측 그래프 $G{\displaystyle }$ ${\displaystyle G}$에 대해$$$\chi {\displaystyle {}_{}^{}}$${\displaystyle g_{}^{}}$ ${\displaystyle {}_{}^{}}$( ${\displaystyle G}$) ${\displaystyle \le }$( ${\displaystyle 2}$- ${\displaystyle ϵ}$) ${\displaystyle \mathrm{\Delta }}$( G${\displaystyle }$) Δ ( ${\displaystyle G}$ ) ${\displaystyle \chi '_{g}(G)\leq (2-\epsilon )\delta (G$
$\Delta {\displaystyle \mathrm{}}$(${\displaystyle G}$) ${\displaystyle \Delta (G)}$이(가) $G{\displaystyle }$ ${\displaystyle G}$의 정점 수와 비교하여 충분히 클 때 이러한 추측이$$ 성립된다$.$^[20]

• 식목성.Let ${\displaystyle a(G)}$ be the arboricity of a graph ${\displaystyle G}$. Every graph ${\displaystyle G}$ with maximum degree ${\displaystyle \Delta (G)}$ has ${\displaystyle \chi '_{g}(G)\leq \Delta (G)+3a(G)-1}$.^[21]

그래프 클래스

For a class ${\displaystyle {\mathcal {C}}}$ of graphs, we denote by ${\displaystyle \chi '_{g}({\mathcal {C}})}$ the smallest integer ${\displaystyle k}$ such that every graph ${\displaystyle G}$ of ${\displaystyle {\mathcal {C}}}$ has ${\displaystyle \chi '$$_{g}(G)\leq k$ 즉 $\chi {\displaystyle {}_{}^{}}$ ${\displaystyle g_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\displaystyle (C}$) ${\displaystyle \chi '_{g}({\mathcal{C})}$는 이 등급의 그래프의 게임 색도 지수에 대한 정확한 상한이다.이 값은 몇 가지 표준 그래프 클래스에 대해 알려져 있으며 일부 다른 클래스에는 한계가 있다.

• 휠$$: $\chi {\displaystyle {}_{}^{}}$ ${\displaystyle \mathrm{g}}$${\displaystyle {}_{}^{}}$ ${\displaystyle ({}_{}}$ ${\displaystyle {3\mathrm{}}_{}}$)$$= 5 ${\$$displaystyle$ $\chi '_{g}(W_{3})=5}$ 및$$ $n{\displaystyle }$${\displaystyle {\chi }_{}^{}}$ g${\displaystyle {}_{}^{}\prime (W_{}}$ n${\displaystyle {}_{}}$)${\displaystyle }$= n${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle \chi '_{g}(W_$${n$$})=n+1$$\}.$^[19]
• Forests : ${\displaystyle \chi '_{g}({\mathcal {F}}_{\Delta })\leq \Delta +1}$ when ${\displaystyle \Delta \neq 4}$, and ${\displaystyle 5\leq \chi '_{g}({\mathcal {F}}_{4})\leq 6}$.^[22]
  또한 F ${\displaystyle 4_{\mathrm{}}}$ ${\$의 $숲{\displaystyle }$ F ${\displaystyle F}$의 모든 트리를 애벌레 나무에서 분할하여 얻거나$$ 4도와 인접한 정점 두 개를 포함하지 않으면 $\chi {\displaystyle {}_{}^{}}$ ${\displaystyle g_{}^{}}$ ${\displaystyle {}_{}^{}}$(${\displaystyle F}$ ${\displaystyle )}$ ${\displaystyle \le }$ ${\displaystyle 5}$ ${\displaysty$ style$\chi '_{g}($F)\$leq$ 5$\}.$^[23]

문제 열기

상한.Is there a constant ${\displaystyle c\geq 2}$ such that ${\displaystyle \chi '_{g}(G)\leq \Delta (G)+c}$ for each graph ${\displaystyle G}$ ? If it is true, is ${\displaystyle c=2}$ enough ?^[19]

최소한도로 추측해봐 There are a ${\displaystyle \epsilon >0}$ and an integer ${\displaystyle d_{0}}$ such that any graph ${\displaystyle G}$ with ${\displaystyle \delta (G)\geq d_{0}}$ satisfies ${\displaystyle \chi '_{g}(G)\geq (1+\epsilon )\delta (G)}$. ^[20]

발생색소 게임

발병률 채색 게임은 안드레스가 소개한 그래프 채색 게임으로,^[24] 앨리스와 밥이 적절한 정점 채색 대신 적절한 발병률 채색을 구성한다는 점을 제외하면 정점 채색 게임과 유사하다.그 규칙은 다음과 같다.

1. Alice와 Bob은 그래프 G의 발생에 색을 칠하고 있다.
2. 앨리스와 밥이 교대로 돌아가면서 무색화 현상(표준 버전에서는 앨리스가 시작된다)을)을 적절히 색칠하고 있다.
3. 만일 어떤 사건 i가 제대로 색칠을 할 수 없다면(어떤 색이든, 나는 그것에 색칠된 사건에 인접해 있다), 밥은 승리한다.
4. 만약 모든 사건들이 적절히 색칠된다면, 앨리스가 승리할 것이다.

${\displaystyle g_{}}$ (${\displaystyle {}_{}G}$) ${\$displaystyle i_{g}(G)}에 의해 표시된 $그래프{\displaystyle }$ G ${\displaystyle$G}의 발생 게임 색수는 $앨리스$가 G$${\$displaystyle G}$에서 이 게임을 이기는데 필요한 최소 색상 수입니다$.$

최대 도 $\Delta {\displaystyle \mathrm{}}$ ${\displaystyle \Delta }$을$($를) $가진{\displaystyle }$모든 $그래프$ G {\$displaystyle$ $}$에 대해 3Δ < $g>$ < - 1 {\$frac${$3\Delta -1}{2}}<i_{g}(G) -1}$가 있다^[24]

다른 관념과의 관계

• (a,d)-디포메이션.이것은 우리가 알고 있는 일반 사례에 대한 최선의 상한선이다.If the edges of a graph ${\displaystyle G}$ can be partitioned into two sets, one of them inducing a graph with arboricity${\displaystyle a}$, the second inducing a graph with maximum degree ${\displaystyle d}$, then ${\displaystyle i_{g}(G)\leq \left\lfloor {$$\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+3d-1}$^[25].
  If moreover ${\displaystyle \Delta (G)\geq 5a+6d}$, then ${\displaystyle i_{g}(G)\leq \left\lfloor {\frac {3\Delta (G)-a}{2}}\right\rfloor +8a+d-1}$.^[25]
• 타락.If ${\displaystyle G}$ is a k-degenerated graph with maximum degree ${\displaystyle \Delta (G)}$, then ${\displaystyle i_{g}(G)\leq 2\Delta (G)+4k-2}$. Moreover, ${\displaystyle i_{g}(G)\leq 2\Delta (G)+3k-1}$ when ${\di$$splaystyle \Delta (G)\geq 5k-1}$ and ${\displaystyle i_{g}(G)\leq \Delta (G)+8k-2}$ when ${\displaystyle \Delta (G)\leq 5k-1}$.^[24]

그래프 클래스

For a class ${\displaystyle {\mathcal {C}}}$ of graphs, we denote by ${\displaystyle i_{g}({\mathcal {C}})}$ the smallest integer ${\displaystyle k}$ such that every graph ${\displaystyle G}$ of ${\displaystyle {\mathcal {C}}}$ has ${\displaystyle i_{g}(G)\leq k}$$$.

• 경로 : $k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 13}$ ${\displaystyle k\geq 13$의 경우, ${\displaystyle \mathrm{i}}$ ${\displaystyle g_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$)${\displaystyle }$= 5 ${\displaystyle i_{g}(P_{k})=5}$.
• 주기 : ${\displaystyle \mathrm{k}}$ ${\displaystyle \ge }$ 3 ${\displaystyle k\geq 3$의 경우, $i{\displaystyle {}_{}}$ ${\displaystyle g_{}{}_{}}$ ${\displaystyle C_{}}$ )${\displaystyle }$= ${\displaystyle 5}$ ${\displaystyle i_{g}(C_{k})=5}$^[26].
• 별 : ${\displaystyle \mathrm{k}}$ ${\displaystyle \ge }$ 1 ${\displaystyle k\geq$ 1$}$의 경우$,$ $i{\displaystyle {}_{}}$ ${\displaystyle g_{}}$ ${\displaystyle {}_{}}$ 2 ${\displaystyle k_{}}$)${\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k}$ ${\displaystyle i_{g}(S_{2k})=3k}$^[24].
• 휠 : $k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 6}$ ${\displaystyle k\geq 6$의 경우, $i{\displaystyle {}_{}}$ ${\displaystyle g_{}{\mathrm{W}}_{}}$ 2 ${\displaystyle {k\mathrm{}}_{}}$+ 1${\displaystyle {}_{}}$)${\displaystyle }$= ${\displaystyle 3}$ k${\displaystyle }$+ ${\displaystyle 2}$ ${\displaystyle i_{g}(W_{2k+1})=3k+2$$k{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle 7}$ ${\displaystyle k\geq$ 7$}$의 경우$,$ $i{\displaystyle {}_{}}$ ${\displaystyle g_{}{}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle k_{}}$)${\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle k}$ ${\displaystyle i_{g}(W_{2k})=3k$^[24]
• Subgraphs of Wheels : For ${\displaystyle k\geq 13}$, if ${\displaystyle G}$ is a subgraph of ${\displaystyle W_{k}}$ having ${\displaystyle S_{k}}$ as a subgraph, then ${\displaystyle i_{g}(G)=\left\lceil {\frac {3k}{2}}\right\rceil }$.^[27]

문제 열기

• 상한 g ()< ( G)- ${\displaystyle i_{g}(G)}<3\Delta (G)-1}$이(가) $\Delta {\displaystyle \mathrm{}}$( ${\displaystyle G}$) ${\displaysty \Delta (G)}$의 모든 값에 대해 조여 있는가?$$^[24]
• 발생 게임 색도 숫자는 단조 파라미터인가?^[24] (즉, G의 하위 그래프와 마찬가지로 그래프 G의 경우 최소 크기인가?)

메모들

참조(만성 순서)