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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 3.149.232.215 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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