The maximum matching width is a width-parameter that is defined by a branch-decomposition over
the vertex set of a graph using the symmetric submodular cut-function obtained by taking the size of a maximum matching of the bipartite graph crossing the cut. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we find the exact value of the maximum matching width of a grid.
Maximum matching width는 그래프의 vertex set에서 정의된 branch-decomposition을 이용한 widthparameter로, branch-decomposition의 각각의 edge cut에서 얻어지는 maximum matching의 크기를 통해 정의된다. 이 parameter는 기존에 잘 알려진 parameter인 treewidth, branchwidth와 linear한 관계가 있으며, 몇몇 문제에 대해서는 이를 사용하여 더 좋은 알고리즘을 찾을 수 있음이 알려져 있다. Robertson-Seymour theorem에 의해, minor operation에 닫혀 있는 모든 그래프로 이루어진 집합은 finite한 minor obstruction set을 가진다. 이 논문에서는 bounded maximum matching width인 graph class가 minor operation에 닫혀 있음을 증명하고, 이를 이용하여 maximum matching width가 2일 필요충분조건을 minor obstruction set을 characterize함으로서 증명한다. 또한 격자판 모양의 grid graph의 정확한 maximum matching width의 값을 계산한다.
