On Hadwiger's number---A problem of the Nordhaus-Gaddum type
type: Item
instance of: scholarly article
title: On Hadwiger's number---A problem of the Nordhaus-Gaddum type
zbMATH Open document ID: 0774.05096
DOI: 10.1016/0012-365X(92)90611-I
author: Michael Stiebitz
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: For a graph \(G\), \(\overline G\) denotes its complement and \(h(G)\) is the maximum order of a clique to which \(G\) can be contracted. Let \(F(n,k)\) denote \(\max h(\overline G)\) for all graphs \(G\) with order \(n\) and \(h(G)=k\). Analogously \(f(n,k)\) is \(\min h(\overline G)\). The values of \(F(n,k)\) for all \(n\) and \(k\) and a lower bound of \(f(n,k)\) for \(2\leq k\leq 3\) are given among others.
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 89911
zbMATH Keywords: Nordhaus-Gaddum type
zbMATH Keywords: contraction
zbMATH Keywords: Hadwiger number
zbMATH Keywords: bound
MaRDI profile type: Publication
cites work: Q3856672
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: On Hadwiger's Number and the Stability Number
cites work: Q3328583
cites work: Q5837979
cites work: Q3701447
cites work: Q4713810
cites work: On a relationship between Hadwiger and stability numbers
cites work: On Complementary Graphs
cites work: Q5528475
cites work: Über eine Eigenschaft der ebenen Komplexe
Recommended article: Q3728018
Recommended article: Q5868819
Recommended article: Q4014618
Recommended article: On the Borsuk and Erdős-Hadwiger numbers
Recommended article: Q4688339
Recommended article: On an additive-number-theoretic problem of P. Erdős
Recommended article: Q3064735
Recommended article: On a Problem of Sidon in Additive Number Theory, and on some Related Problems
Recommended article: On some generalizations of Horadam’s numbers
Recommended article: Some nordhaus‐‐ gaddum‐type results
description: scientific article; zbMATH DE number 89911