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
|
|
Author(s): |
| 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
|
|
|
Abstract: |
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
|
