Problem 17.3: Cochromatic Number
The paper [Y. Caro, On The Covering Number Of Combinatorial Structures,
Ars Combin. 29B (1990) 111-124] investigates the
cochromatic number in a general combinatorial setting.
In particular it contains new results on general upper bounds, and
results that relate the cochromatic number to perfection and independence
number of a graph. An interesting stronger version of the theorem of
Nordhaus and Gaddum [1956] (see Problem 6.11) is also presented.
August 13, 1997. Tommy R. Jensen
Problem 17.3 has been solved in the paper:
N. Alon, M. Krivelevich and B. Sudakov, Subgraphs with a Large
Cochromatic Number, J. Graph Theory 25 (1997), 295-297.
August 14, 1997. Tommy R. Jensen and Bjarne Toft
Last modified August 14, 1997 Tommy R. Jensen