List-Distinguishing Cartesian Products of CliquesDiscrete Mathematics (2019)
The distinguishing number of a graph G, denoted D(G), is the minimum number of colors needed to produce a coloring of the vertices of G so that every nontrivial isomorphism interchanges vertices of different colors. A list assignment L on a graph G is a function that assigns each vertex of G a set of colors. An L-coloring of G is a coloring in which each vertex is colored with a color from L(v). The list distinguishing number of G, denoted Dℓ(G) is the minimum k such that every list assignment L that assigns a list of size at least k to every vertex permits a distinguishing L-coloring. In this paper, we prove that when and n is large enough, the distinguishing and list-distinguishing numbers of Kn□Km agree for almost all m>n, and otherwise differ by at most one. As a part of our proof, we give (to our knowledge) the first application of the Combinatorial Nullstellensatz to the graph distinguishing problem and also prove an inequality for the binomial distribution that may be of independent interest.
- list distinguishing
Publication DateJuly, 2019
Citation InformationMichael Ferrara, Zoltan Füredi, Sogol Jahanbekam and Paul Wenger. "List-Distinguishing Cartesian Products of Cliques" Discrete Mathematics Vol. 342 Iss. 7 (2019) p. 2012 - 2022 ISSN: 0012-365X
Available at: http://works.bepress.com/sogol-jahanbekam/2/