“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 622
School of Mathematics
  Title:   Minimal coloring and strength of graphs
1.  R. Tusserkani
2.  H. Hajiabolhassan
3.  M. L. Mehrabadi
  Status:   Published
  Journal: Discrete Math.
  No.:  1-3
  Vol.:  215
  Year:  2000
  Pages:   265-270
  Supported by:  IPM
Let G be a graph. A minimal coloring of G is a coloring which has the smallest possible sum among all proper colorings of G, using natural numbers. The vertex-strength of G, denoted by s(G), is the minimum number of colors which is necessary to obtain a minimal coloring. In this note we study these concepts, and define a new concept called the edge-strength of G, denoted by s′(G). We pose some upper bounds for s(G) using ∆(G) and col(G). Also, it is proved that s′(G) lies between ∆(G) and ∆(G)+1, but it may not be equal to X′(G). Based on our results on vertex-strength, we conjecture that:
s(G) ≤ ⎡\dfracX (G)+∆(G)2⎤.

Download TeX format
back to top
scroll left or right