Pairs of disjoint matchings and related classes of graphs

Guo, Huizheng; Kaempen, Kieran; Mo, Zhengda; Qunell, Sam; Rogge, Joe; Song, Chao; Tserunyan, Anush; Zomback, Jenna

doi:10.2140/involve.2023.16.249

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Pairs of disjoint matchings and related classes of graphs

Huizheng Guo, Kieran Kaempen, Zhengda Mo, Sam Qunell, Joe Rogge, Chao Song, Anush Tserunyan and Jenna Zomback

Vol. 16 (2023), No. 2, 249–264

DOI: 10.2140/involve.2023.16.249

Abstract

For a finite graph $G$ , we study the maximum $2$ -edge colorable subgraph problem and a related ratio $μ (G) ∕ ν (G)$ , where $ν (G)$ is the matching number of $G$ , and $μ (G)$ is the size of the largest matching in any pair $(H, H^{'})$ of disjoint matchings maximizing $| H | + | H^{'} |$ (equivalently, forming a maximum $2$ -edge colorable subgraph). Previously, it was shown that $\frac{4}{5} \leq μ (G) ∕ ν (G) \leq 1$ , and the class of graphs achieving $\frac{4}{5}$ was completely characterized. We show here that any rational number between $\frac{4}{5}$ and $1$ can be achieved by a connected graph. Furthermore, we prove that every graph with ratio less than $1$ must admit special subgraphs.

Keywords

graph, matching, edge coloring, maximum 2-edge colorable subgraph

Mathematical Subject Classification

Primary: 05C70

Milestones

Received: 7 July 2021

Revised: 8 May 2022

Accepted: 8 May 2022

Published: 26 May 2023

Communicated by Ronald Gould

Authors

Huizheng Guo
Department of Mathematics The George Washington University Washington, DC United States

Kieran Kaempen
Department of Computer Science University of Illinois Urbana-Champaign Urbana, IL United States

Zhengda Mo
Department of Mathematics University of Illinois Urbana-Champaign Urbana, IL United States

Sam Qunell
Department of Mathematics University of California Los Angeles, CA United States

Joe Rogge
Department of Mathematics University of Washington Seattle, WA United States

Chao Song
Department of Mathematics University of Illinois Urbana-Champaign Urbana, IL United States

Anush Tserunyan
Mathematics and Statistics Department McGill University Montreal, QC Canada

Jenna Zomback
Department of Mathematics University of Illinois Urbana-Champaign Urbana, IL United States

Vol. 16, No. 2, 2023