“School of Computer Science”
Back to Papers HomeBack to Papers of School of Computer Science
| Paper IPM / Computer Science / 10977 |
|
||||||
| Abstract: | |||||||
|
The chromatic sum of a graph is the minimum total of the colors on the vertices taken over all possible proper colorings using positive integers. Erd�s et al [Graphs that require many colors to achieve their chromatic sum, Congr. Numer. 71 (1990) 17-28.] considered the question of finding graphs with minimum number of vertices that require t colors beyond their chromatic number k to obtain their chromatic sum. The number of vertices of such graphs is denoted by P(k, t). They presented some upper bounds for this parameter by introducing certain constructions. In this paper we give some lower bounds for P(k, t) and considerably improve the upper bounds by introducing a class of graphs, called tabular graphs. Finally, for fixed t and sufficiently large k the exact value of P(k, t) is determined.
Download TeX format |
|||||||
| back to top | |||||||
