受賞区分：国際学会・会議・シンポジウム等の賞  受賞国：台湾

担当区分：筆頭著者,　責任著者   記述言語：英語   掲載種別：研究論文（大学，研究機関等紀要）  

担当区分：筆頭著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Journal of Graph Theory  

In matching theory, one of the most fundamental and classical branches of combinatorics, canonical decompositions of graphs are powerful and versatile tools that form the basis of this theory. However, the abilities of the known canonical decompositions, that is, the Dulmage–Mendelsohn, Kotzig–Lovász, and Gallai–Edmonds decompositions, are limited because they are only applicable to particular classes of graphs, such as bipartite graphs, or they are too sparse to provide sufficient information. To overcome these limitations, we introduce a new canonical decomposition that is applicable to all graphs and provides much finer information. This decomposition also provides the answer to the longstanding absence of a canonical decomposition that is nontrivially applicable to general graphs with perfect matchings. We focus on the notion of factor-components as the fundamental building blocks of a graph; through the factor-components, our new canonical decomposition states how a graph is organized and how it contains all the maximum matchings. The main results that constitute our new theory are the following: (i) a canonical partial order over the set of factor-components, which describes how a graph is constructed from its factor-components; (ii) a generalization of the Kotzig–Lovász decomposition, which shows the inner structure of each factor-component in the context of the entire graph; and (iii) a canonically described interrelationship between (i) and (ii), which integrates these two results into a unified theory of a canonical decomposition. These results are obtained in a self-contained way, and our proof of the generalized Kotzig–Lovász decomposition contains a shortened and self-contained proof of the classical counterpart.

DOI： 10.1002/jgt.23190

Open Access

Web of Science

Scopus

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： https://doi.org/10.1016/j.dam.2022.08.024

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（大学，研究機関等紀要）  

担当区分：筆頭著者,　最終著者,　責任著者   記述言語：英語   掲載種別：研究論文（大学，研究機関等紀要）  

開催年月日： 2025年3月

記述言語：英語   会議種別：口頭発表（一般）  

開催地：Boca Raton, FL