<p>A graph <i>G</i> is <i>k</i> list equitably colorable, if for any given <i>k</i>-uniform list assignment <i>L</i>, <i>G</i> is <i>L</i>-colorable and each color appears on at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq1.gif" Format="GIF" Height="25" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(\lceil \frac{|V(G)|}{k}\rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌈</mo> <mfrac> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> <mi>k</mi> </mfrac> <mo>⌉</mo> </mrow> </math></EquationSource> </InlineEquation> vertices. Kostochka et al. conjectured that if <i>G</i> is a connected graph with maximum degree at least 3, then <i>G</i> is <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <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> list equitably colorable, unless <i>G</i> is a complete graph or is <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{k,k}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi>k</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> for some odd <i>k</i>. An equitable <i>k</i>-coloring <i>c</i> of <i>G</i> is a mapping <i>c</i> from <i>V</i>(<i>G</i>) to <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="133" /> </InlineMediaObject> <EquationSource Format="TEX">\([k]=\{1,2,\ldots ,k\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>k</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(c(u)\ne c(v)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>≠</mo> <mi>c</mi> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for each <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="80" /> </InlineMediaObject> <EquationSource Format="TEX">\(uv\in E(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mi>v</mi> <mo>∈</mo> <mi>E</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and for each <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="16" /> </InlineMediaObject> <EquationSource Format="TEX">\(k_i\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>k</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">\(k_j \in [k]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>k</mi> <mi>j</mi> </msub> <mo>∈</mo> <mrow> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq9.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="281" /> </InlineMediaObject> <EquationSource Format="TEX">\(||\{v|c(v)=k_i\}|-|\{w|c(w)=k_j\}||\le 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> <mo stretchy="false">|</mo> </mrow> <mrow> <mo stretchy="false">{</mo> <mi>v</mi> <mo stretchy="false">|</mo> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>k</mi> <mi>i</mi> </msub> <mo stretchy="false">}</mo> </mrow> <mrow> <mo stretchy="false">|</mo> <mo>-</mo> <mo stretchy="false">|</mo> </mrow> <mrow> <mo stretchy="false">{</mo> <mi>w</mi> <mo stretchy="false">|</mo> <mi>c</mi> <mrow> <mo stretchy="false">(</mo> <mi>w</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mi>k</mi> <mi>j</mi> </msub> <mo stretchy="false">}</mo> </mrow> <mrow> <mo stretchy="false">|</mo> <mo stretchy="false">|</mo> </mrow> <mo>≤</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Chen et al. conjectured that each connected graph with maximum degree <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> that is different from the complete graph <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq11.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{\Delta +1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>, the complete bipartite graph <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{\Delta , \Delta }\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi mathvariant="normal">Δ</mi> <mo>,</mo> <mi mathvariant="normal">Δ</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> and an odd cycle admits an equitable coloring with <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq10.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> colors. In this paper, we prove that if <i>G</i> is a planar graph without 5-cycles, then <i>G</i> is <i>k</i> list equitably colorable and equitably <i>k</i>-colorable where <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="26_2025_748_Article_IEq14.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="138" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\ge \max \{\Delta (G),7\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mo movablelimits="true">max</mo> <mo stretchy="false">{</mo> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mn>7</mn> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Equitable and List Equitable Colorings of Planar Graphs Without 5-Cycles

  • Aijun Dong,
  • Wenwen Zhang

摘要

A graph G is k list equitably colorable, if for any given k-uniform list assignment L, G is L-colorable and each color appears on at most \(\lceil \frac{|V(G)|}{k}\rceil \) | V ( G ) | k vertices. Kostochka et al. conjectured that if G is a connected graph with maximum degree at least 3, then G is \(\Delta (G)\) Δ ( G ) list equitably colorable, unless G is a complete graph or is \(K_{k,k}\) K k , k for some odd k. An equitable k-coloring c of G is a mapping c from V(G) to \([k]=\{1,2,\ldots ,k\}\) [ k ] = { 1 , 2 , , k } such that \(c(u)\ne c(v)\) c ( u ) c ( v ) for each \(uv\in E(G)\) u v E ( G ) , and for each \(k_i\) k i , \(k_j \in [k]\) k j [ k ] , \(||\{v|c(v)=k_i\}|-|\{w|c(w)=k_j\}||\le 1\) | | { v | c ( v ) = k i } | - | { w | c ( w ) = k j } | | 1 . Chen et al. conjectured that each connected graph with maximum degree \(\Delta \) Δ that is different from the complete graph \(K_{\Delta +1}\) K Δ + 1 , the complete bipartite graph \(K_{\Delta , \Delta }\) K Δ , Δ and an odd cycle admits an equitable coloring with \(\Delta \) Δ colors. In this paper, we prove that if G is a planar graph without 5-cycles, then G is k list equitably colorable and equitably k-colorable where \(k\ge \max \{\Delta (G),7\}\) k max { Δ ( G ) , 7 } .