On the mean chromatic number (Q1322240): Difference between revisions

From the article: ``Taking the colors to be the positive integers, the greedy vertex-coloring algorithm can be described as follows. The vertices of a graph \(G\) are ordered and the algorithm assigns colors to the vertices in that order, giving each vertex the first ... color which has not already been assigned to a vertex adjacent to it.'' The article cites results from the literature about the worst case performance of this algorithm and then discusses its average-case performance (over all vertex-orders) for two families of graphs: cocktail party graphs \((K_{n,n}\) with a 1-factor removed) and even cycles. A formula is given for the proportion of orders for which the greedy algorithm will use at least \(i\) colors too many, and asymptotic results are given which show that the number of colors used tends to 2 for the cocktail party graphs and to 3 for even cycles.