Upper Bounds for the List-Distinguishing Chromatic Number
Amitayu Banerjee, Zalán Molnár, Alexa Gopaulsingh · Graphs and Combinatorics · 2025
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)$$ Δ ( 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.