“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 165 |
|
| 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 | |
