Subset matching and edge coloring in bipartite graphs
| dc.contributor.author | Yavuzyılmaz, Ömer Can | |
| dc.contributor.author | Kayaaslan, Enver | |
| dc.date.accessioned | 2025-10-24T18:06:40Z | |
| dc.date.available | 2025-10-24T18:06:40Z | |
| dc.date.issued | 2016 | |
| dc.department | Malatya Turgut Özal Üniversitesi | |
| dc.description.abstract | The focus of this paper is on finding a matching in a bipartite graph such that a given subset of vertices are matched. This is called subset matching and generalizes perfect matchings. We prove a necessary and sufficient condition for the existence of a subset matching in bipartite graphs. The proof is algorithmic and based on combination of two matchings. Remarkably, the necessary and sufficient condition always holds when the subset is composed of the vertices with maximum degree. This in turn leads to a simple algorithm that finds an optimal edge coloring in bipartite graphs with no need to transform the bipartite graph into a regular one. © 2016 Elsevier B.V., All rights reserved. | |
| dc.identifier.doi | 10.1016/j.endm.2016.10.031 | |
| dc.identifier.endpage | 126 | |
| dc.identifier.issn | 1571-0653 | |
| dc.identifier.scopus | 2-s2.0-84995578342 | |
| dc.identifier.scopusquality | N/A | |
| dc.identifier.startpage | 123 | |
| dc.identifier.uri | https://doi.rog/10.1016/j.endm.2016.10.031 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12899/3124 | |
| dc.identifier.volume | 55 | |
| dc.indekslendigikaynak | Scopus | |
| dc.language.iso | en | |
| dc.publisher | Elsevier B.V. | |
| dc.relation.ispartof | Electronic Notes in Discrete Mathematics | |
| dc.relation.publicationcategory | Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı | |
| dc.rights | info:eu-repo/semantics/closedAccess | |
| dc.snmz | Scopus_20251023 | |
| dc.subject | bipartite graph | |
| dc.subject | edge coloring | |
| dc.subject | matching | |
| dc.title | Subset matching and edge coloring in bipartite graphs | |
| dc.type | Article |
