Lower bound of the hadwiger number of graphs by their average degree

A. V. Kostochka

doi:10.1007/BF02579141

Lower bound of the hadwiger number of graphs by their average degree

Research output: Contribution to journal › Article › peer-review

Abstract

The aim of this paper is to show that the minimum Hadwiger number of graphs with average degree k is O(k/√log k). Specially, it follows that Hadwiger's conjecture is true for almost all graphs with n vertices, furthermore if k is large enough then for almost all graphs with n vertices and nk edges.

Original language	English (US)
Pages (from-to)	307-316
Number of pages	10
Journal	Combinatorica
Volume	4
Issue number	4
DOIs	https://doi.org/10.1007/BF02579141
State	Published - Dec 1984
Externally published	Yes

Keywords

AMS subject classification 1980): 05C10, 05C15, 60C05

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Online availability

10.1007/BF02579141

Library availability

Discover UIUC Full Text

Cite this

@article{cf1c2b8556b542dbbdb36e51061e6ade,

title = "Lower bound of the hadwiger number of graphs by their average degree",

abstract = "The aim of this paper is to show that the minimum Hadwiger number of graphs with average degree k is O(k/√log k). Specially, it follows that Hadwiger's conjecture is true for almost all graphs with n vertices, furthermore if k is large enough then for almost all graphs with n vertices and nk edges.",

keywords = "AMS subject classification 1980): 05C10, 05C15, 60C05",

author = "Kostochka, {A. V.}",

year = "1984",

month = dec,

doi = "10.1007/BF02579141",

language = "English (US)",

volume = "4",

pages = "307--316",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Lower bound of the hadwiger number of graphs by their average degree

AU - Kostochka, A. V.

PY - 1984/12

Y1 - 1984/12

N2 - The aim of this paper is to show that the minimum Hadwiger number of graphs with average degree k is O(k/√log k). Specially, it follows that Hadwiger's conjecture is true for almost all graphs with n vertices, furthermore if k is large enough then for almost all graphs with n vertices and nk edges.

AB - The aim of this paper is to show that the minimum Hadwiger number of graphs with average degree k is O(k/√log k). Specially, it follows that Hadwiger's conjecture is true for almost all graphs with n vertices, furthermore if k is large enough then for almost all graphs with n vertices and nk edges.

KW - AMS subject classification 1980): 05C10, 05C15, 60C05

UR - http://www.scopus.com/inward/record.url?scp=51249184988&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249184988&partnerID=8YFLogxK

U2 - 10.1007/BF02579141

DO - 10.1007/BF02579141

M3 - Article

AN - SCOPUS:51249184988

SN - 0209-9683

VL - 4

SP - 307

EP - 316

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Lower bound of the hadwiger number of graphs by their average degree

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this