We prove that for a fixed integer
s$
p = r^{{1 + \frac{1}
{{2{\left( {a - 1} \right)}}} + o{\left( 1 \right)}}}
$
p = r^{{1 + \frac{1}
{{2{\left( {a - 1} \right)}}} + o{\left( 1 \right)}}}
. A well-known conjecture on the existence of dense
K
s,s
-free graphs would imply that the value of the exponent is best possible. Our result implies Hadwiger
s conjecture for
K
s,s
-free graphs whose chromatic number is sufficiently large compared with
s.
Mathematics Subject Classification (2000):
05C83 - 05C35 - 05D40