Independence number and clique minors

    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