2017/05/21 by Mohammad Abdolmaleki, M. Abdolmaleki, Joan P. Hutchinson +11
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C15
paper · pdf · doi:10.48550/arxiv.1705.07434
arxiv created 2017/05/21 · openalex publication_date 2017/05/21 · arxiv updated 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G is called uniquely k-list colorable (UkLC) if there exists a list of colors on its vertices, say L=\lbrace Sv | v ∈ V(G) \rbrace , each of size k, such that there is a unique proper list coloring of G from this list of colors. A graph G is said to have property M(k) if it is not uniquely k-list colorable. Mahmoodian and Mahdian characterized all graphs with property M(2). For k≥ 3 property M(k) has been studied only for multipartite graphs. Here we find bounds on M(k) for graphs embedded on surfaces, and obtain new results on planar graphs. We begin a general study of bounds on M(k) for regular graphs, as well as for graphs with varying list sizes.