Tabular graphs and chromatic sum

AbstractThe 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