Lower bound of the Hadwiger number of graphs by their average degree
type: Item
instance of: scholarly article
title: Lower bound of the Hadwiger number of graphs by their average degree
zbMATH Open document ID: 0555.05030
DOI: 10.1007/BF02579141
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: A contraction of a connected graph \(G=(V,E)\) to the complete graph with r vertices is considered as a surjection \(\psi: V\to \{1,2,...,r\}\) with the properties that every subgraph of G induced by \(\psi^{-1}(i)\) is connected and for any integers i, j from \(\{\) 1,2,...,r\(\}\), \(i\neq j\), there exist vertices \(v\in \psi^{-1}(i)\) and \(w\in \psi^{-1}(j)\) such that \((v,w)\in E.\) the greatest r such that G can be contracted onto the complete graph with r vertices is called the Hadwiger number \(\eta\) (G) of G. The minimum of \(\eta\) (G) for graphs \(G=(V,E)\) with \(| E| /| V| \geq k\) is denoted by \(\eta\) (k). Further for each positive integer k the function \(w(k)=\min \{\eta (G): \chi (G)\geq k\}.\) The well- known conjecture of Hadwiger says that \(w(k)=k\) for any k. In the present paper it is proved that \(\eta (k)\geq k/270\sqrt{\log k}\) and \(w(k)\geq k/540\sqrt{\log k}\) for \(k\geq 2\). From this corollary follows that if k is large enough, then Hadwiger's conjecture is true for almost all graphs with n vertices and kn edges.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 3884189
zbMATH Keywords: contraction
zbMATH Keywords: complete graph
zbMATH Keywords: Hadwiger number
zbMATH Keywords: Hadwiger's conjecture
author: Alexandr Kostochka
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
Wikidata QID: Q56235110
cites work: Q4065548
cites work: Q5837979
cites work: On the minimum of the Hadwiger number for graphs with a given mean degree of vertices
cites work: Homomorphiesätze für Graphen
cites work: Contractions of graphs: A theorem of Ore and an extremal problem
cites work: Beweis einer Abschwächung der Hadwiger-Vermutung
cites work: On some graph-theoretical problems of V. G. Vizing
full work available at URL: https://doi.org/10.1007/bf02579141
OpenAlex ID: W2047993669
Recommended article: Q2975718
Recommended article: Q5497164
Recommended article: On the average lower bondage number of a graph
Recommended article: Q5377838
Recommended article: A lower bound on the average size of a connected vertex set of a graph
Recommended article: Q2975669
Recommended article: On the minimum of the Hadwiger number for graphs with a given mean degree of vertices
Recommended article: The average lower connectivity of graphs
Recommended article: Q3333070
Recommended article: On average lower independence and domination numbers in graphs
description: scientific article; zbMATH DE number 3884189