Greedy algorithms for \(T\)-colorings of complete graphs and the meaningfulness of conclusions about them. (English) Zbl 0774.05037

Cozzens, Margaret B.; Roberts, Fred S.

J. Comb. Inf. Syst. Sci. 16, No. 4, 286-299 (1991).

Summary: The theory of meaningfulness of scales of measurement can be used to put limitations on the types of statements we should make about the conclusions we draw in combinatorial optimization. In this paper, we study the generalization of ordinary graph coloring called \(T\)-coloring and investigate conclusions about \(T\)-coloring which arose from an attempt to apply the theory of meaningfulness. In particular, we show that under a certain assumption about the scales of measurement used (that they are all ratio scales), it can be meaningless to conclude that the greedy algorithm obtains an optimal \(T\)-coloring for the complete graph \(K_ n\) for fixed \(n\). However, it is meaningful to conclude that the greedy algorithm obtains an optimal \(T\)-coloring for the complete graph \(K_ n\) for all \(n\). That is, it is possible for the greedy algorithm to obtain an optimal \(T\)-coloring for a particular \(K_ n\) while the greedy algorithm does not obtain an optimal \(sT\)-coloring for \(K_ n\), where \(s\) is a positive integer. However, if the greedy algorithm obtains an optimal \(T\)-coloring for all \(K_ n\) then the greedy algorithm obtains an optimal \(sT\)-coloring for all \(K_ n\).

MSC:

05C15	Coloring of graphs and hypergraphs
05C85	Graph algorithms (graph-theoretic aspects)

Keywords:

optimal \(T\)-coloring; graph coloring; greedy algorithm; complete graph