Title

Independence number and clique minors

Authors

Authors

K. I. Kawarabayashi;Z. X. Song

Comments

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

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

Language

English

First Page

219

Last Page

226

WOS Identifier

WOS:000250209500004

ISSN

0364-9024

Share

COinS