Dense minors of graphs with independence number two

Sergey Norin; Paul Seymour

doi:10.1016/j.jctb.2025.08.005

Dense minors of graphs with independence number two

Sergey Norin, Paul Seymour

Mathematics

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

Abstract

Motivated by Hadwiger's conjecture, we prove that every graph with no independent set of size three contains a t-vertex simple minor with 0.98688⋅(t2)−o(t²) edges, where t is its chromatic number.

Original language	English (US)
Pages (from-to)	101-110
Number of pages	10
Journal	Journal of Combinatorial Theory. Series B
Volume	176
DOIs	https://doi.org/10.1016/j.jctb.2025.08.005
State	Published - Jan 2026

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Graph minors
Hadwiger's conjecture
Independence number

Access to Document

10.1016/j.jctb.2025.08.005

Cite this

@article{3ffbeea502c3419cb30adabf7dba4b9f,

title = "Dense minors of graphs with independence number two",

abstract = "Motivated by Hadwiger's conjecture, we prove that every graph with no independent set of size three contains a t-vertex simple minor with 0.98688⋅(t2)−o(t2) edges, where t is its chromatic number.",

keywords = "Graph minors, Hadwiger's conjecture, Independence number",

author = "Sergey Norin and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2025 Elsevier Inc.",

year = "2026",

month = jan,

doi = "10.1016/j.jctb.2025.08.005",

language = "English (US)",

volume = "176",

pages = "101--110",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Dense minors of graphs with independence number two

AU - Norin, Sergey

AU - Seymour, Paul

PY - 2026/1

Y1 - 2026/1

N2 - Motivated by Hadwiger's conjecture, we prove that every graph with no independent set of size three contains a t-vertex simple minor with 0.98688⋅(t2)−o(t2) edges, where t is its chromatic number.

AB - Motivated by Hadwiger's conjecture, we prove that every graph with no independent set of size three contains a t-vertex simple minor with 0.98688⋅(t2)−o(t2) edges, where t is its chromatic number.

KW - Graph minors

KW - Hadwiger's conjecture

KW - Independence number

UR - https://www.scopus.com/pages/publications/105015850297

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

U2 - 10.1016/j.jctb.2025.08.005

DO - 10.1016/j.jctb.2025.08.005

M3 - Article

AN - SCOPUS:105015850297

SN - 0095-8956

VL - 176

SP - 101

EP - 110

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Dense minors of graphs with independence number two

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this