#### Title

Independence number and clique minors

#### Abbreviated Journal Title

J. Graph Theory

#### Keywords

Hadwiger's conjecture; independence number; graph minor; EVERY PLANAR MAP; HADWIGER CONJECTURE; Mathematics

#### Abstract

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 Title

Journal of Graph Theory

#### Volume

56

#### Issue/Number

3

#### Publication Date

1-1-2007

#### Document Type

Article

#### DOI Link

#### Language

English

#### First Page

219

#### Last Page

226

#### WOS Identifier

#### ISSN

0364-9024

#### Recommended Citation

"Independence number and clique minors" (2007). *Faculty Bibliography 2000s*. 7291.

http://stars.library.ucf.edu/facultybib2000/7291

## Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu