<p>The <i>b</i>-fold indicated <i>L</i>-coloring game on <i>G</i> is played by two players: Ann and Ben, where <i>G</i> is a graph and <i>L</i> is a list assignment of <i>G</i>. In each round, Ann chooses an uncolored vertex <i>v</i>, and Ben colors <i>v</i> with a <i>b</i>-set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\phi (v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> from <i>L</i>(<i>v</i>) such that none of the colors in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\phi (v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> have been used by its colored neighbors. If all vertices are colored, Ann wins the game. Otherwise, after some rounds, there is an uncolored vertex <i>v</i> with less than <i>b</i> available colors (i.e., colors in its list not used by its colored neighbors), and Ben wins the game. We say <i>G</i> is indicated (<i>L</i>,&#xa0;<i>b</i>)-colorable if Ann has a winning strategy for the <i>b</i>-fold indicated <i>L</i>-coloring game. For a mapping <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(g: V(G) \rightarrow \mathbb {N}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <mo>:</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">N</mi> </mrow> </math></EquationSource> </InlineEquation>, we say <i>G</i> is indicated (<i>g</i>,&#xa0;<i>b</i>)<i>-choosable </i>if <i>G</i> is indicated (<i>L</i>,&#xa0;<i>b</i>)-colorable for every list assignment <i>L</i> of <i>G</i> with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(|L(v)|\ge g(v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>L</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>≥</mo> <mi>g</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for each vertex <i>v</i>. If <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(g(v)=a\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>g</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mi>a</mi> </mrow> </math></EquationSource> </InlineEquation> for every vertex <i>v</i>, then indicated (<i>g</i>,&#xa0;<i>b</i>)-choosable is called indicated (<i>a</i>,&#xa0;<i>b</i>)-choosable. The indicated choice number <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(ch_i(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the least integer <i>k</i> such that <i>G</i> is indicated (<i>k</i>,&#xa0;1)-choosable (also called indicated <i>k</i>-choosable). The fractional indicated choice number of <i>G</i> is <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(ch_i^f(G)=\inf \{\frac{a}{b}:G\text { is indicated } (a,b)\text {-choosable}\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msubsup> <mi>h</mi> <mi>i</mi> <mi>f</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo movablelimits="true">inf</mo> <mrow> <mo stretchy="false">{</mo> <mfrac> <mi>a</mi> <mi>b</mi> </mfrac> <mo>:</mo> <mi>G</mi> <mspace width="0.333333em" /> <mtext>is indicated</mtext> <mspace width="0.333333em" /> <mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo>,</mo> <mi>b</mi> <mo stretchy="false">)</mo> </mrow> <mtext>-choosable</mtext> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. This paper proves that for any finite graph <i>G</i>, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(ch_i^f(G)=ch_i(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <msubsup> <mi>h</mi> <mi>i</mi> <mi>f</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>c</mi> <msub> <mi>h</mi> <mi>i</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>; a connected graph <i>G</i> is indicated 2-choosable if and only if its core is <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(K_1\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\( \Theta _{2,2,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="normal">Θ</mi> <mrow> <mn>2</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> or an even cycle; for <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\( m \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, a graph <i>G</i> is indicated (2<i>m</i>,&#xa0;<i>m</i>)-choosable if and only if <i>G</i> is a tree. A graph <i>G</i> is called <i>indicated</i> <i>k</i><i>-choosable-critical</i> if <i>G</i> is not indicated <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\((k-1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-choosable, but any proper subgraph is indicated <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\((k-1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-choosable. We give a characterization of indicated 3-choosable critical graphs.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Indicated multifold-choosability of graphs

  • Jiacheng Zhu,
  • Xuding Zhu,
  • Zhanghao Zhu

摘要

The b-fold indicated L-coloring game on G is played by two players: Ann and Ben, where G is a graph and L is a list assignment of G. In each round, Ann chooses an uncolored vertex v, and Ben colors v with a b-set \(\phi (v)\) ϕ ( v ) from L(v) such that none of the colors in \(\phi (v)\) ϕ ( v ) have been used by its colored neighbors. If all vertices are colored, Ann wins the game. Otherwise, after some rounds, there is an uncolored vertex v with less than b available colors (i.e., colors in its list not used by its colored neighbors), and Ben wins the game. We say G is indicated (Lb)-colorable if Ann has a winning strategy for the b-fold indicated L-coloring game. For a mapping \(g: V(G) \rightarrow \mathbb {N}\) g : V ( G ) N , we say G is indicated (gb)-choosable if G is indicated (Lb)-colorable for every list assignment L of G with \(|L(v)|\ge g(v)\) | L ( v ) | g ( v ) for each vertex v. If \(g(v)=a\) g ( v ) = a for every vertex v, then indicated (gb)-choosable is called indicated (ab)-choosable. The indicated choice number \(ch_i(G)\) c h i ( G ) is the least integer k such that G is indicated (k, 1)-choosable (also called indicated k-choosable). The fractional indicated choice number of G is \(ch_i^f(G)=\inf \{\frac{a}{b}:G\text { is indicated } (a,b)\text {-choosable}\}\) c h i f ( G ) = inf { a b : G is indicated ( a , b ) -choosable } . This paper proves that for any finite graph G, \(ch_i^f(G)=ch_i(G)\) c h i f ( G ) = c h i ( G ) ; a connected graph G is indicated 2-choosable if and only if its core is \(K_1\) K 1 or \( \Theta _{2,2,2}\) Θ 2 , 2 , 2 or an even cycle; for \( m \ge 2\) m 2 , a graph G is indicated (2mm)-choosable if and only if G is a tree. A graph G is called indicated k-choosable-critical if G is not indicated \((k-1)\) ( k - 1 ) -choosable, but any proper subgraph is indicated \((k-1)\) ( k - 1 ) -choosable. We give a characterization of indicated 3-choosable critical graphs.