Subset matching and edge coloring in bipartite graphs

详细信息    查看全文

• 作者：Ö ; mer Can Yavuzyılmaz ^{omercanyy@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Enver Kayaaslan ^{ekayaaslan@turgutozal.edu.tr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：bipartite graph ; matching ; edge coloring
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：55
• 期：Complete
• 页码：123-126
• 全文大小：162 K

文摘

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.