COLORING A GRAPH OPTIMALLY WITH 2 COLORS

Let G be a graph with point set V. A (2-)coloring of G is a map of V t o {rcd, white}. An error occurs whenever the two endpoints of a line h ave the same color. An optimal coloring of G is a coloring of G for wh ich the number of errors is minimum. The minimum number of errors is d enoted by gamma(G), we derive upper and lower bounds for gamma(G) and prove that if G is a graph with n points and m lines, then max {0, m- 1/4n2!} less-than-or-equal-to gamma(G) less-than-or-equal-to 1/2m-1/4 (h(m)-1!, where h(m)=min{n/m less-than-or-equal-to (n/2)}. The lower b ound is sharp, and for infinitely many values of m the upper bound is attained for all sufficiently large n.