Award type：Award from international society, conference, symposium, etc.  Country：Taiwan, Province of China

Authorship：Lead author,　Corresponding author   Language：English   Publishing type：Research paper (bulletin of university, research institution)  

Authorship：Lead author,　Corresponding author   Language：English   Publishing type：Research paper (scientific journal)   Publisher：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

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (scientific journal)  

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

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (bulletin of university, research institution)  

Authorship：Lead author,　Last author,　Corresponding author   Language：English   Publishing type：Research paper (bulletin of university, research institution)  

Event date： 2025.3

Language：English   Presentation type：Oral presentation (general)  

Venue：Boca Raton, FL