Upper bounds for the list-distinguishing chromatic number

2024/05/21 by Amitayu Banerjee, Banerjee, Amitayu, Zalán Molnár +2 · 1 citation
Computer Science · #05C07 #05C15 #05C25 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2405.12733

openalex publication_date 2024/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove analogs of Brooks' Theorem for the list-distinguishing chromatic number of different classes of simple finite connected graphs. Moreover, we determine two upper bounds for the list-distinguishing chromatic number of a graph 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 various families of graphs (for example: the book graphs).

Cited by

• The List-distinguishing chromatic number of graphs containing only small complete bigraphs

Related

• The List-distinguishing chromatic number of graphs containing only small complete bigraphs
• The list-chromatic number and the coloring number of uncountable graphs
• The list chromatic number of graphs with small clique number
• Nordhaus-Gaddum Theorem for the Distinguishing Chromatic Number
• List edge-colouring and total colouring in graphs of low treewidth