ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 MS Classification: 05 Mahmoodian, Ebadollah S., Sharif University of Technology, I. R. Iran Defining sets in graph colorings In this talk we will briefly survey some results on a concept in graph colorings called defining set. In a given graph G, a set of vertices S with an assignment of colors is said to be a defining set of vertex coloring, if there exists a unique extension for the colors of S to a χ(G)-coloring of vertices of G. A defining set for edge coloring and also for total coloring is defined similarly. The concept of defining set has been studied in block designs and, under the name, critical sets in Latin squares and Room squares. A connection with the latter topic will be mentioned. The same as critical sets in Latin squares, one may consider applications of defining sets of graphs in cryptography. References: E. S. Mahmoodian, R. Naserasr, and M. Zaker, Defining sets of vertex coloring of graphs and Latin rectangles, Discrete Math., 167/168 (1997), 451–460.