Title

Independence Number And Clique Minors

Keywords

Graph minor; Hadwiger's conjecture; Independence number

Abstract

The Hadwiger number h(G) of a graph G is the maximum integer f such that Kt is a minor of G. Since ξ(G) ̇ α (G) > |G|, Hadwiger's conjecture implies that h(G) · α(G) > |G|, where α(G) and |G| denote the independence number and the number of vertices of G1 respectively. Motivated by this fact, it is shown that (2a(G) - 2) · h(G) > |G| for every graph G with α (G) > 3. This improves a theorem of Duchet and Meyniel and a recent improvement due to Kawarabayashi et al. © 2007 Wiley Periodicals, Inc.

Publication Date

1-1-2007

Publication Title

Journal of Graph Theory

Volume

56

Issue

3

Number of Pages

219-226

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1002/jgt.20268

Socpus ID

35948944311 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/35948944311

This document is currently not available here.

Share

COinS