Publications of (and about) Paul Erdös
Autor: Bollobás, Béla; Catlin, Paul A.; Erdös, Pál
Title: Hadwiger's conjecture is true for almost every graph. (In English)
Source: Eur. J. Comb. 1, 195-199 (1980).
Review: From the abstract: The contradiction clique number ccl(G) of a graph G is the maximal r for which G has a subcontraction to the complete graph Kr. We prove that for d > 2, almost every graph of order n satisfies n((log2n) ½ +4)-1 \leq ccl(G) \leq n(log2n-d log2 log2n)- ½ . This inequality implies the statement in the title.
Classif.: * 05C35 Extremal problems (graph theory)
05C15 Chromatic theory of graphs and maps
Keywords: Hadwiger's conjecture; contraction clique number
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag