On a relationship between Hadwiger and stability numbers
type: Item
instance of: scholarly article
title: On a relationship between Hadwiger and stability numbers
zbMATH Open document ID: 0628.05052
DOI: 10.1016/0012-365X(87)90238-X
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: It was proved that the inequality \(\eta\) (G)(2\(\alpha\) (G)-1)\(\geq n(G)\) holds for any graph G, where \(\eta\) (G) is the Hadwiger number of G, \(\alpha\) (G) is the stability number of G, and n(G) is the number of vertices, and it was conjectured that the inequality \(\eta\) (G)\(\cdot \alpha (G)\geq n(G)\) holds for any graph G. In this note, the authors prove that the equality holds in the first inequality if and only if G is a complete graph, and that the second inequality holds for any graph if and only if the inequality \(\eta\) (G)\(\cdot \alpha (G)\geq n(G)-C\) holds for any graph G and any given constant C. Two new parameters related to it are also defined and discussed.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4021192
zbMATH Keywords: Hadwiger number
zbMATH Keywords: stability number
author: Frédéric Maffray
author: Henri Meyniel
reviewed by: Weixuan Li
MaRDI profile type: Publication
cites work: Q5615282
cites work: On Hadwiger's Number and the Stability Number
cites work: Q3333070
cites work: Homomorphiesätze für Graphen
cites work: An extremal function for contractions of graphs
description: scientific article; zbMATH DE number 4021192