The strength of a graph G is the smallest integers such that there exists a minimum sum coloring of G using integers {1, ... , s}, only. For bipartite graphs of maximum degree Delta we show the following simple bound: s <= inverted right perpendicular Delta/2inverted left perpendicular + 1. As a consequence, there exists a quadratic time algorithm for determining the strength and minimum color sum of bipartite graphs of maximum degree Delta <= 4.
展开▼
