×

List-distinguishing Cartesian products of cliques. (English) Zbl 1414.05250

Summary: 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 automorphism 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_{\ell}(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 \(n\) is large enough, the distinguishing and list-distinguishing numbers of \(K_n\square K_m\) 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 setting of distinguishing graph colorings and also prove an inequality for the binomial distribution that may be of independent interest.

MSC:

05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Albertson, M., Distinguishing cartesian powers of graphs, Electron. J. Combin., 12 (2005), Note 17, 5 pp. (electronic) · Zbl 1082.05047
[2] Albertson, M.; Collins, K. L., Symmetry breaking in graphs, Electron. J. Combin., 3, 1 (1996), Research Paper 18, 17 pp. (electronic) · Zbl 0851.05088
[3] Alon, N., Combinatorial nullstellensatz, recent trends in combinatorics, Combin. Probab. Comput., 8, 7-29 (1999)
[4] Arvind, V.; Cheng, C.; Devanur, N., On computing the distinguishing numbers of planar graphs and beyond: a counting approach, SIAM J. Discrete Math., 22, 1297-1324 (2008) · Zbl 1226.05210
[5] L. Babai, Graph isomorphism in quasipolynomial time, 89 pp. arXiv preprint arXiv:1512.03547; L. Babai, Graph isomorphism in quasipolynomial time, 89 pp. arXiv preprint arXiv:1512.03547
[6] Babai, L., On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comput., 9, 212-216 (1980) · Zbl 0446.68052
[7] Babai, L.; Erdős, P.; Selkow, S., Random graph isomorphisms, SIAM J. Comput., 9, 628-635 (1980) · Zbl 0454.05038
[8] Beckenbach, E.; Bellman, R., Inequalities (1961), Springer-Verlag: Springer-Verlag New York · Zbl 0186.09606
[9] Burris, A.; Schelp, R., Vertex-distinguishing proper edge-colorings, J. Graph Theory, 26, 73-82 (1997) · Zbl 0886.05068
[10] Cheng, C., On computing the distinguishing numbers of trees and forests, Electron. J. Combin., 13 (2006), Research Paper 11, 12 pp · Zbl 1080.05081
[11] Cheng, C., On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results, Discrete Math., 309, 5169-5182 (2009) · Zbl 1213.05071
[12] Erdős, P.; Rubin, A.; Taylor, H., Choosability in graphs, Congr. Numer., 26, 125-157 (1980)
[13] Ferrara, M.; Flesch, B.; Gethner, E., List-distinguishing colorings of graphs, Electron. J. Combin., 18 (2011), Paper 161, 17 pp · Zbl 1230.05127
[14] Ferrara, M.; Gethner, E.; Hartke, S.; Stolee, D.; Wenger, P., List distinguishing parameters of trees, Discrete Appl. Math., 161, 864-869 (2013) · Zbl 1262.05050
[15] Ferrara, M.; Gethner, E.; Hartke, S.; Stolee, D.; Wenger, P., Extending procolorings to distinguish group actions, European J. Combin., 72, 12-28 (2018) · Zbl 1390.05065
[16] Fisher, M.; Isaak, G., Distinguishing colorings of cartesian products of complete graphs, Discrete Math., 308, 2240-2246 (2008) · Zbl 1147.05029
[17] Immel, P.; Wenger, P., The list distinguishing number equals the distinguishing number for interval graphs, Discuss. Math. Graph Theory, 37, 165-174 (2017) · Zbl 1354.05086
[18] Imrich, W.; Jerebic, J.; Klavžar, S., The distinguishing number of cartesian products of complete graphs, European J. Combin., 29, 922-929 (2008) · Zbl 1205.05198
[19] Karpovsky, M.; Chakrabarty, K.; Levitin, L., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44, 599-611 (1998) · Zbl 1105.94342
[20] Klavžar, S.; Zhu, X., Cartesian powers of graphs can be distinguished by two labels, European J. Combin., 28, 303-310 (2007) · Zbl 1105.05032
[21] Lehner, F., Distinguishing graphs with intermediate growth, Combinatorica, 36, 333-347 (2016) · Zbl 1389.05070
[22] Rubin, F., Problem 729, J. Recreat. Math., 11, 128 (1979)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.