Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  457.05041
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.
Reviewer:  E.Palmer
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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page