Independence number and clique minors
Abbreviated Journal Title
J. Graph Theory
Hadwiger's conjecture; independence number; graph minor; EVERY PLANAR MAP; HADWIGER CONJECTURE; Mathematics
The Hadwiger number h(G) of a graph G is the maximum integer t such that K-t is a minor of G. Since X(G) . alpha(G) >= vertical bar G vertical bar, Hadwiger's conjecture implies that h(G) . alpha(G) >= vertical bar G vertical bar, where alpha(G) and vertical bar G vertical bar denote the independence number and the number of vertices of G, respectively. Motivated by this fact, it is shown that (2 alpha(G) - 2) . h(G) >= vertical bar G vertical bar for every graph G with alpha(G) >= 3. This improves a theorem of Duchet and Meyniel and a recent improvement due to Kawarabayashi et al. (c) 2007 Wiley Periodicals, Inc.
Journal of Graph Theory
"Independence number and clique minors" (2007). Faculty Bibliography 2000s. 7291.