Dense Matchings of Linear Size in Graphs with Independence Number 2

Jung Hon Yip · 2025

Read Dense Matchings of Linear Size in Graphs with Independence Number 2 by Jung Hon Yip (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-01401.txt.

Description

Jung Hon Yip proves a claim about dense matchings in a class of graphs. A matching pairs up points in a graph with edges. The class here has independence number at most two. That means any three points hold at least one edge among them.

For large graphs in that class, Yip finds a matching of set size. He also bounds how many non-adjacent pairs the matching can leave. Dense matchings help in tasks like pairing users or jobs. A firm proof for this class adds a tool for cases where the graph is near-complete.

Catalog record

CREATORJung Hon Yip
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE23 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-01401

Browse the full library · About the Tower of Babel