Subset matching and edge coloring in bipartite graphs
Küçük Resim Yok
Tarih
2016
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier B.V.
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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.
Açıklama
Anahtar Kelimeler
bipartite graph, edge coloring, matching
Kaynak
Electronic Notes in Discrete Mathematics
WoS Q Değeri
Scopus Q Değeri
N/A
Cilt
55
