2024/09/08 by Rong Chen, Chen, Rong, Zijian Deng +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2409.05920
openalex publication_date 2024/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A matching M in a graph G is \em connected if G has an edge linking each pair of edges in M. The problem to find large connected matchings in graphs G with α(G)=2 is closely related to Hadwiger's conjecture for graphs with independence number 2. The problem of finding a large connected matching in a general graph is NP-hard. Füredi et al. in 2005 conjectured that each (4t-1)-vertex graph G with α(G)=2 contains a connected matching of size at least t. Cambie recently showed that if this conjecture is false, then so is Hadwiger's conjecture. In this paper, we present a number of properties possessed by a counterexample to Füredi et al.'s conjecture, and then using these properties, we prove that Füredi et al.'s conjecture holds for t≤22.