“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 165
School of Mathematics
  Title:   Defining sets and uniqueness in graph colorings: A survey
  Author(s):  E. S. Mahmoodian
  Status:   Published
  Journal: J. Statist. Plann. Inference
  Vol.:  73
  Year:  1998
  Pages:   85-89
  Supported by:  IPM
  Abstract:
There are different ways of coloring a graph, namely vertex coloring, edge coloring, total coloring, list coloring, etc. Literature is full of fascinating papers and even books and monographs on this subject. This note will briefly survey some results on two concepts in graph colorings. First we discuss the uniqueness of graph colorings and then we introduce the concept of defining sets on this subject. For example, 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. The concept of defining set has been studied to some extent about the block designs and also under the other name, a critical set, about latin 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.

Download TeX format
back to top
scroll left or right