<p>In this paper, all results apply only to finite graphs. Let <i>G</i> be a simple connected finite graph with <i>n</i> vertices and maximum degree <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq1.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>. We show that the list-distinguishing chromatic number <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{D_{L}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <msub> <mi>D</mi> <mi>L</mi> </msub> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of <i>G</i> is at most <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(2\Delta (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, and it is <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">\(2\Delta (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> if <i>G</i> is a complete bipartite graph <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq5.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="76" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{\Delta (G),\Delta (G)}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>,</mo> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </msub> </math></EquationSource> </InlineEquation> or a cycle with six vertices. We apply a result of Lovász to reduce the above-mentioned upper bound of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{D_{L}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <msub> <mi>D</mi> <mi>L</mi> </msub> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for certain graphs. We also show that if <i>H</i> is a connected unicyclic graph of girth of at least seven and <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta (H)\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, then <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="58" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{D_{L}}(H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <msub> <mi>D</mi> <mi>L</mi> </msub> </msub> <mrow> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is at most <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(\Delta (H)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Moreover, we obtain two upper bounds for <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2920_Article_IEq2.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="56" /> </InlineMediaObject> <EquationSource Format="TEX">\(\chi _{D_{L}}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>χ</mi> <msub> <mi>D</mi> <mi>L</mi> </msub> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in terms of the coloring number of <i>G</i> and the list chromatic number of <i>G</i>. We also determine the list-distinguishing chromatic number for some special graphs.</p>

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

Upper Bounds for the List-Distinguishing Chromatic Number

  • Amitayu Banerjee,
  • Zalán Molnár,
  • Alexa Gopaulsingh

摘要

In this paper, all results apply only to finite graphs. Let G be a simple connected finite graph with n vertices and maximum degree \(\Delta (G)\) Δ ( G ) . We show that the list-distinguishing chromatic number \(\chi _{D_{L}}(G)\) χ D L ( G ) of G is at most \(2\Delta (G)\) 2 Δ ( G ) , and it is \(2\Delta (G)\) 2 Δ ( G ) if G is a complete bipartite graph \(K_{\Delta (G),\Delta (G)}\) K Δ ( G ) , Δ ( G ) or a cycle with six vertices. We apply a result of Lovász to reduce the above-mentioned upper bound of \(\chi _{D_{L}}(G)\) χ D L ( G ) for certain graphs. We also show that if H is a connected unicyclic graph of girth of at least seven and \(\Delta (H)\ge 3\) Δ ( H ) 3 , then \(\chi _{D_{L}}(H)\) χ D L ( H ) is at most \(\Delta (H)\) Δ ( H ) . Moreover, we obtain two upper bounds for \(\chi _{D_{L}}(G)\) χ D L ( G ) in terms of the coloring number of G and the list chromatic number of G. We also determine the list-distinguishing chromatic number for some special graphs.