Upper Bounds for the List-Distinguishing Chromatic Number

Abstract 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . We show that the list-distinguishing chromatic number $$\chi _{D_{L}}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>D</mml:mi> <mml:mi>L</mml:mi> </mml:msub> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> of G is at most $$2\Delta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , and it is $$2\Delta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> if G is a complete bipartite graph $$K_{\Delta (G),\Delta (G)}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>,</mml:mo> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:msub> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>D</mml:mi> <mml:mi>L</mml:mi> </mml:msub> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , then $$\chi _{D_{L}}(H)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>D</mml:mi> <mml:mi>L</mml:mi> </mml:msub> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is at most $$\Delta (H)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Δ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>H</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . Moreover, we obtain two upper bounds for $$\chi _{D_{L}}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>χ</mml:mi> <mml:msub> <mml:mi>D</mml:mi> <mml:mi>L</mml:mi> </mml:msub> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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.