2015/09/14 by Poppy Immel, Immel, Poppy, Paul S. Wenger +1
Computer Science · #05C60 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.1509.04327
openalex publication_date 2015/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A \distinguishing coloring of a graph G is a coloring of the\nvertices so that every nontrivial automorphism of G maps some vertex to a\nvertex with a different color. The \distinguishing number of G is the\nminimum k such that G has a distinguishing coloring where each vertex is\nassigned a color from 1,\…,k . A \list assignment to G is an\nassignment L= L(v) v\∈ V(G) of lists of colors to the vertices of G.\nA \distinguishing L-coloring of G is a distinguishing coloring of\nG where the color of each vertex v comes from L(v). The it list\ndistinguishing number of G is the minimum k such that every list\nassignment to G in which |L(v)|=k for all v\∈ V(G) yields a\ndistinguishing L-coloring of G. We prove that if G is an interval graph,\nthen its distinguishing number and list distinguishing number are equal.\n