• 1
  • 2
  • 3
  • 4
IPM
30
YEARS OLD

“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 113
School of Mathematics
  Title:   A characterization of uniquely vertex colorable graphs using minimal defining sets
  Author(s): 
1 . H. Hajiabolhassan
2 . M.L. Mehrabadi
3 . R. Tusserkani
4 . M. Zaker
  Status:   Published
  Journal: Discrete Math.
  Vol.:  199
  Year:  1999
  Pages:   233-236
  Supported by:  IPM
  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
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right