An indicated coloring game on a graph G is a variant of a coloring game, which is played by two players, Ann and Ben, with a fixed color set. In each round, Ann indicates an uncolored vertex and then Ben assigns to the vertex a color that has not been assigned to any of its neighbors. Ann aims to achieve a proper coloring of G, while Ben tries to prevent this. The minimum number of colors required for Ann to win the indicated coloring game on a graph G is denoted by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\chi _i(G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. Unlike Brooks’ theorem for ordinary colorings, there are only a few known sufficient conditions for graphs G to have <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\chi _i(G) \le \Delta (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi mathvariant="normal">Δ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Delta (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is the maximum degree of G. In this paper, we pose a conjecture stating that for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$k \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and a connected non-complete k-regular graph G, if G does not contain <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$K_{k+1} -e$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>-</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\chi _i (G) \le k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>. We also show two partial solutions; The conjecture holds if we replace <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$K_{k+1} -e$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo>-</mo> <mi>e</mi> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$K_{\lceil k/2 \rceil +1}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mo>⌈</mo> <mi>k</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo>⌉</mo> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>, or if <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$k=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.

Brooks’ Type Theorem for Indicated Coloring Game

期刊论文
发表日期：

2025年10月3日

查看全文

Haruki Kawabe,
Yosuke Kobayashi,
Shieri Kojima,
Kenta Ozeki

摘要

An indicated coloring game on a graph G is a variant of a coloring game, which is played by two players, Ann and Ben, with a fixed color set. In each round, Ann indicates an uncolored vertex and then Ben assigns to the vertex a color that has not been assigned to any of its neighbors. Ann aims to achieve a proper coloring of G, while Ben tries to prevent this. The minimum number of colors required for Ann to win the indicated coloring game on a graph G is denoted by $\chi _i(G)$ $χ_{i} (G)$ . Unlike Brooks’ theorem for ordinary colorings, there are only a few known sufficient conditions for graphs G to have $\chi _i(G) \le \Delta (G)$ $χ_{i} (G) \leq Δ (G)$ , where $\Delta (G)$ $Δ (G)$ is the maximum degree of G. In this paper, we pose a conjecture stating that for $k \ge 3$ $k \geq 3$ and a connected non-complete k-regular graph G, if G does not contain $K_{k+1} -e$ $K_{k + 1} - e$ , then $\chi _i (G) \le k$ $χ_{i} (G) \leq k$ . We also show two partial solutions; The conjecture holds if we replace $K_{k+1} -e$ $K_{k + 1} - e$ with $K_{\lceil k/2 \rceil +1}$ $K_{⌈ k / 2 ⌉ + 1}$ , or if $k=3$ $k = 3$ .