Thin edges in claw-free bricks

Jinxin Xue ; Fuliang Lu

The electronic journal of combinatorics, Tome 32 (2025) no. 3

Résumé

A brick is a non-bipartite matching covered graph without nontrivial tight cuts. The importance of bricks stems from the fact that they are building blocks of the matching covered graphs. The bi-contraction of a vertex $u$ of degree two in a graph $G$, with precisely two neighbors $u_1$ and $u_2$, consists of shrinking the set $\{u, u_1,u_2\}$ to a single vertex. The retract of a matching covered graph $G$ is the graph obtained from $G$ by repeatedly bi-contracting vertices of degree two. An edge $e$ of a brick $G$ is thin if the retract of $G-e$ is a brick. By showing the existence of thin edge in every brick (other than three basic bricks), Carvalho et al. presented inductive tools for building all the bricks from three basic bricks. However, the lower bound of the number of thin edges in a brick is still unknown. In this paper, we provide the first nontrivial family of graphs, the numbers of thin edges of which are not a constant: we show that every claw-free brick $G$ with at least 8 vertices has at least $3|V(G)|/8$ thin edges. Consequently, we prove that every claw-free minimal brick $G$ has at least $3|V(G)|/16$ cubic vertices, which shows that Norine and Thomas's conjecture about linear bound of the number of cubic vertices in minimal bricks [J. Combin. Theory Ser. B, 96(4) (2006)] holds for claw-free minimal bricks.

Détail

DOI : 10.37236/12976

Classification : 05C70, 05C75
Mots-clés : bicritical graph, brick, matching covered graph, perfect matching