<p>For a graph <i>G</i> with a list assignment <i>L</i> and two <i>L</i>-colorings <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation>, an <i>L</i>-recoloring sequence from <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\beta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>β</mi> </math></EquationSource> </InlineEquation> is a sequence of proper <i>L</i>-colorings where consecutive colorings differ at exactly one vertex. We prove the existence of such a recoloring sequence in which every vertex is recolored at most a constant number of times under two conditions: (i) <i>G</i> is planar, contains no 3-cycles or intersecting 4-cycles, and <i>L</i> is a 6-assignment; or (ii) the maximum average degree of <i>G</i> satisfies <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\textrm{mad}(G) &lt; \frac{5}{2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>mad</mtext> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <mfrac> <mn>5</mn> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation> and <i>L</i> is a 4-assignment. These results strengthen two theorems previously established by Cranston.</p>

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

List Recoloring of Two Classes of Planar Graphs

  • Chenran Pan,
  • Weifan Wang,
  • Runrun Liu

摘要

For a graph G with a list assignment L and two L-colorings \(\alpha \) α and \(\beta \) β , an L-recoloring sequence from \(\alpha \) α to \(\beta \) β is a sequence of proper L-colorings where consecutive colorings differ at exactly one vertex. We prove the existence of such a recoloring sequence in which every vertex is recolored at most a constant number of times under two conditions: (i) G is planar, contains no 3-cycles or intersecting 4-cycles, and L is a 6-assignment; or (ii) the maximum average degree of G satisfies \(\textrm{mad}(G) < \frac{5}{2}\) mad ( G ) < 5 2 and L is a 4-assignment. These results strengthen two theorems previously established by Cranston.