From 6659c33a805c0e22c969a45480c068d5d7ddf471 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 3 May 2008 21:27:02 +0200
Subject: [PATCH] References to better bounds for enforced minors.

---
 adv.tex    | 17 ++++++++++++-----
 biblio.bib | 22 ++++++++++++++++++++++
 2 files changed, 34 insertions(+), 5 deletions(-)

diff --git a/adv.tex b/adv.tex
index b21a363..09670b6 100644
--- a/adv.tex
+++ b/adv.tex
@@ -76,7 +76,7 @@ Let $G$ be a~graph and $\cal C$ be a class of graphs. We define the \df{edge den
 $\varrho(G)$ of~$G$ as the average number of edges per vertex, i.e., $m(G)/n(G)$. The
 edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\varrho(G)$ over all $G\in\cal C$.
 
-\thmn{Mader \cite{mader:dens}}
+\thmn{Mader \cite{mader:dens}}\id{maderthm}%
 For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
 of average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph.
 
@@ -124,10 +124,6 @@ edges, its average degree would be at least~$h(x)$, so by the previous theorem
 $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor.
 \qed
 
-\rem
-Minor-closed classes share many other interesting properties, for example bounded chromatic
-numbers of various kinds, as shown by Theorem 6.1 of \cite{nesetril:minors}.
-
 Let us return to the analysis of our algorithm.
 
 \thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}%
@@ -265,6 +261,17 @@ The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt \
 who studied a~parallel version of the Contractive Bor\o{u}vka's algorithm applied
 to minor-closed classes.
 
+\rem
+The bound on the average degree needed to enforce a~$K_k$ minor, which we get from Theorem \ref{maderthm},
+is very coarse. Kostochka \cite{kostochka:lbh} and independently Thomason \cite{thomason:efc}
+have proven that an~average degree $\Omega(k\sqrt{\log k})$ is sufficient and that this
+is the best what we can get.
+
+\rem
+Minor-closed classes share many other interesting properties, for example bounded chromatic
+numbers of various kinds, as shown by Theorem 6.1 of \cite{nesetril:minors}. We can expect
+that many algorithmic problems will turn out to be easy for them.
+
 %--------------------------------------------------------------------------------
 
 \section{Iterated algorithms}\id{iteralg}%
diff --git a/biblio.bib b/biblio.bib
index a2cbfa0..9a40c05 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -1594,3 +1594,25 @@
  publisher = {ACM},
  address = {New York, NY, USA},
 }
+
+@article{ kostochka:lbh,
+  title={{Lower bound of the hadwiger number of graphs by their average degree}},
+  author={Kostochka, A.V.},
+  journal={Combinatorica},
+  volume={4},
+  number={4},
+  pages={307--316},
+  year={1984},
+  publisher={Springer}
+}
+
+@article{ thomason:efc,
+  title={{An extremal function for contractions of graphs}},
+  author={Thomason, A.},
+  journal={Mathematical proceedings of the Cambridge Philosophical Society},
+  volume={95},
+  number={2},
+  pages={261--265},
+  year={1984},
+  publisher={Cambridge University Press}
+}
-- 
2.39.2