1Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece. 2Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea. 3School of Computing, KAIST, Daejeon, South Korea
The electronic journal of combinatorics, Tome 32 (2025) no. 1
Perfect matching width is a treewidth-like parameter designed for graphs with perfect matchings. The concept was originally introduced by Norine for the study of non-bipartite Pfaffian graphs. Additionally, perfect matching width appears to be a useful structural tool for investigating matching minors, a specialised version of minors related to perfect matchings. In this paper we lay the groundwork for understanding the interaction of perfect matching width and matching minors by establishing tight connections between the perfect matching width of any matching covered graph $G$ and the perfect matching width of its bricks and braces (a matching theoretic version of blocks) and proving that perfect matching width is almost monotone under the matching minor relation. As an application, we give several characterisations for braces of perfect matching width two, including one that allows for a polynomial time recognition algorithm.
Archontia C. Giannopoulou
1
;
Meike Hatzel
2
;
Sebastian Wiederrecht
3
1
Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece.
2
Discrete Mathematics Group, Institute for Basic Science (IBS), Daejeon, South Korea.
3
School of Computing, KAIST, Daejeon, South Korea
@article{10_37236_10716,
author = {Archontia C. Giannopoulou and Meike Hatzel and Sebastian Wiederrecht},
title = {Braces of perfect matching width 2},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/10716},
zbl = {1560.05103},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10716/}
}
TY - JOUR
AU - Archontia C. Giannopoulou
AU - Meike Hatzel
AU - Sebastian Wiederrecht
TI - Braces of perfect matching width 2
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10716/
DO - 10.37236/10716
ID - 10_37236_10716
ER -
%0 Journal Article
%A Archontia C. Giannopoulou
%A Meike Hatzel
%A Sebastian Wiederrecht
%T Braces of perfect matching width 2
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10716/
%R 10.37236/10716
%F 10_37236_10716
Archontia C. Giannopoulou; Meike Hatzel; Sebastian Wiederrecht. Braces of perfect matching width 2. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/10716
