A chain theorem for planar PM-compact bricks
Abstract
A connected graph G is matching covered if it contains at least one edge and every edge belongs to some perfect matching of G. A matching covered graph is a brick if it is 3-connected and after removing any two vertices, the resulting graph has a perfect matching. Bricks are the building blocks of matching covered graphs. A brick G is extremal if the incidence vectors of all perfect matchings are linearly independent over ℝ. Zhou et al. [On planar extremal nonsolid bricks, J. Graph Theory, 2026] proved that for every planar extremal brick G, there exists a sequence of planar extremal bricks G0,G1,…,Gn such that the underlying graph of Gn is an odd wheel, G0=G, and each Gi (0≤ i < n) has a triangle Ti such that Gi/Ti = Gi+1, where Gi/Ti means contracting the triangle Ti into a single vertex. In this paper, the result of Zhou et al. is generalized to planar PM-compact bricks, a larger class of bricks including extremal bricks. We present a chain theorem for planar PM-compact bricks: for every planar PM-compact brick G, there exists a sequence of planar PM-compact bricks G0,G1,…,Gn such that the underlying graph of Gn is an odd wheel, G0=G, and each Gi (0≤ i < n) contains a triangle Ti such that Gi/Ti = Gi+1.
Related
- A graded version of the separator theorem for planar graphs
- A comparison theorem for the planar strip isoperimetric problem
- A centerpoint theorem for three planar convex bodies
- A planar algebraic Zarankiewicz theorem over prime fields
- Spectral theorem for compact self-adjoint operators on smooth Banach spaces
BibTeX
@misc{zhang2026chain,
title = {{A chain theorem for planar PM-compact bricks}},
author = {Yaxian zhang and Qiuli Li and Fuliang Lu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15534},
eprint = {2610.15534},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15534},
}
RIS
TY - UNPB
TI - A chain theorem for planar PM-compact bricks
AU - Yaxian zhang
AU - Qiuli Li
AU - Fuliang Lu
PY - 2026
DA - 2026/10/11
PB - arXiv
DO - 10.48550/arxiv.2610.15534
UR - https://arxiv.org/abs/2610.15534
AB - A connected graph G is matching covered if it contains at least one edge and every edge belongs to some perfect matching of G. A matching covered graph is a brick if it is 3-connected and after removing any two vertices, the resulting graph has a perfect matching. Bricks are the building blocks of matching covered graphs. A brick G is extremal if the incidence vectors of all perfect matchings are linearly independent over ℝ. Zhou et al. [On planar extremal nonsolid bricks, J. Graph Theory, 2026] proved that for every planar extremal brick G, there exists a sequence of planar extremal bricks G_0,G_1,…,G_n such that the underlying graph of G_n is an odd wheel, G_0=G, and each G_i (0≤ i < n) has a triangle T_i such that G_i/T_i = G_i+1, where G_i/T_i means contracting the triangle T_i into a single vertex. In this paper, the result of Zhou et al. is generalized to planar PM-compact bricks, a larger class of bricks including extremal bricks. We present a chain theorem for planar PM-compact bricks: for every planar PM-compact brick G, there exists a sequence of planar PM-compact bricks G_0,G_1,…,G_n such that the underlying graph of G_n is an odd wheel, G_0=G, and each G_i (0≤ i < n) contains a triangle T_i such that G_i/T_i = G_i+1.
ER -