Dense Matchings of Linear Size in Graphs with Independence Number 2

2025/12/01 by Yip, Jung Hon · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2512.01401

Abstract

For a real number c > 4, we prove that every graph G with α(G) ≤ 2 and |V(G)| ≥ ct has a matching M with |M| = t such that the number of non-adjacent pairs of edges in M is at most: ( (1)/(c(c-1)²) + O_c(t^-1/3 ) ) \binomt2. This is related to an open problem of Seymour (2016) about Hadwiger's Conjecture, who asked if there is a constant ε > 0 such that every graph G with α(G) ≤ 2 has had(G) ≥ ((1)/(3) + ε) |V(G)|.

Citations

• Finding dense minors using average degree
• Linear-sized minors with given edge density
• Dense minors of graphs with independence number two
• Hadwiger's conjecture implies a conjecture of Füredi-Gyárfás-Simonyi
• A note on Hadwiger's Conjecture for W₅-free graphs with independence number two

Cited by

• Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2

Related

• Counting Perfect Matchings in Dense Graphs Is Hard
• Connected matching in graphs with independence number two
• Matchings and Independent Sets of a Fixed Size in Regular Graphs
• Matchings in regular graphs: minimizing the partition function
• Nearly Complete Graphs Decomposable into Large Induced Matchings and\n their Applications