“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 113 |
|
||||||||
| Abstract: | |||||||||
|
A defining set (of vertex coloring) of a graph G is a set of vertices S with an assignment of colors to its elements which has a unique completion to a proper coloring of G. We define a minimal defining set to be a defining set which does not properly contain another
defining set. If G is a uniquely vertex colorable graph, clearly its minimum defining sets are of size χ(G)−1. It is shown that for a coloring of G, if all minimal defining sets of G are of size χ(G)−1, then G is a uniquely vertex colorable graph.
Download TeX format |
|||||||||
| back to top | |||||||||
