Separating Matchings in Cubic Graphs
Renzo Gómez, Juan Gutierrez · 2026
Read Separating Matchings in Cubic Graphs by Renzo Gómez, Juan Gutierrez (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17226.txt.
Introduction
Gutiérrez and Gómez study separating matchings in graphs — matchings whose removal splits the graph — bounding the largest such matching. Every subcubic graph admits one except eight graphs, focusing the work on cubic graphs. Every cubic graph admitting one has maximum at least half its vertices minus 2. For bipartite cubic graphs, assuming Funk's conjecture, the problem reduces to a recursive class F, with maximum at least half its vertices minus 1, up to four exceptions. Every claw-free cubic graph has maximum exactly half its vertices.
Catalog record
| CREATOR | Renzo Gómez, Juan Gutierrez |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39517 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.17226
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Separating Matchings in Cubic Graphs Renzo Gómez, Juan Gutierrez Abstract We study separating matchings in graphs, that is, matchings whose removal increases the number of connected components, and focus on determining the maximum size of such a matching in a graph G G , denoted by mms ( G ) \mathrm{mms}(G) . We show that every subcubic graph admits a separating matching, except for exactly eight graphs, which allows us to focus on bounding mms ( G ) \mathrm{mms}(G) for cubic graphs. Our main results show that every cubic graph G G on n n vertices that admits a separating matching satisfies mms ( G ) ≥ n / 2 − 2 \mathrm{mms}(G)\geq n/2-2 . For bipartite cubic graphs, assuming a conjecture of Funk, the problem reduces to a recursively defined class ℱ \mathcal{F} , for which we prove that mms ( G ) ≥ n / 2 − 1 \mathrm{mms}(G)\geq n/2-1 , up to four exceptional graphs. In contrast, we show that every claw-free cubic graph satisfies mms ( G ) = n / 2 \mathrm{mms}(G)=n/2 . These results extend previous work on matching cuts and disconnected 2 2 -factors, and provide the first systematic study of maximum separating matchings. 1 Introduction In this paper, all graphs are simple, and we use standard terminology and notation [ 1 , 4 ] . A classical result due to Petersen states that every cubic bridgeless graph has a perfect matching, and hence a 2 -factor. A natural question is whether such a graph admits a disconnected 2 -factor, that is, a 2 -factor that is not a Hamilton cycle. Diwan [ 5 ] proved that every planar cubic bridgeless graph on at least six vertices has a disconnected 2 -factor. Equivalently, every such graph admits a disconnecting perfect matching , that is, a perfect matching whose removal increases the number of connected components. We study an optimization version of this problem: determine the maximum size of a separating matching in a graph, that is, a matching whose removal increases the number of connected components. We denote this parameter by \mathrm{mms}(G) , and if G has no separating matching, we set \mathrm{mms}(G)=0 . Although this problem has not been studied explicitly, the related notion of a matching cut has received considerable attention [ 2 , 13 , 11 , 12 , 14 , 15 , 18 ] . A matching cut is a matching that is also an edge cut. While not every graph admits such a structure, the existence of a separating matching is equivalent to the existence of a matching cut; graphs with this property are called decomposable . The study of decomposable graphs was initiated by Graham [ 8 ] . Chvátal [ 3 ] showed that recognizing decomposable graphs is polynomial-time solvable for subcubic graphs, but NP-complete for graphs of maximum degree 4 . The problem is also polynomial-time solvable for graphs of radius at most 2 [ 14 ] , and NP-complete for graphs of diameter 3 [ 11 ] . For bipartite graphs, it is polynomial-time solvable when the diameter is at most 3 , and NP-complete when the diameter is 4 [ 11 ] . Moshi [ 16 ] proved that every subcubic graph on at least 8 vertices is decomposable. We strengthen this result as follows. Theorem 1 . Every subcubic graph is decomposable, except for the eight graphs in Figure 1 . This allows us to focus on bounding \mathrm{mms}(G) for cubic graphs. In particular, Diwan’s result can be restated as follows. Theorem 2 (Diwan [ 5 ] ) . If G is a planar cubic bridgeless graph on at least 6 vertices, then \mathrm{mms}(G)=n/2 . Let \nu(G) denote the size of a maximum matching in G . If a cubic graph contains a bridge, we can bound \mathrm{mms}(G) as follows. Theorem 3 . If G is a decomposable cubic graph with a bridge, then \mathrm{mms}(G)\geq\nu(G)-1 . Proof. Let M be a maximum matching in G , and let e be a bridge of G . If e\in M , then M separates G . Otherwise, write e=uv . Since M is maximum, at least one edge of M is incident to u or v . If exactly one such edge e^{\prime} exists, define M^{\prime}=(M\setminus\{e^{\prime}\})\cup\{e\} . If there are two such edges e^{\prime} and e^{\prime\prime} , define M^{\prime}=(M\setminus\{e^{\prime},e^{\prime\prime}\})\cup\{e\} . In both cases, M^{\prime} is a separating matching and |M^{\prime}|\geq|M|-1 . ∎ Restricting to 2 -edge-connected cubic graphs, we obtain the following result. Theorem 4 . For every 2 -edge-connected decomposable cubic graph G on n vertices, \mathrm{mms}(G)\geq n/2-2 . For bipartite cubic graphs, a conjecture of Funk [ 6 ] states that the class of graphs that do not admit a disconnecting perfect matching coincides with a recursively defined class \mathcal{F} . Thus, under this conjecture, bounding \mathrm{mms}(G) for bipartite cubic graphs reduces to understanding graphs in \mathcal{F} . We prove the following. Theorem 5 . For every graph G\in\mathcal{F} on n vertices, \mathrm{mms}(G)\geq n/2-1 , except for the four graphs in Figure 6 . Our final result concerns claw-free cubic graphs. It is known that every connected claw-free graph with an even number of vertices has a perfect matching [ 10 , 20 ] , and in particular this holds for connected claw-free cubic graphs. We strengthen this by showing that such a graph always admits a disconnecting perfect matching. Theorem 6 . Every connected claw-free cubic graph distinct from K_{4} has a disconnecting perfect matching. 2 Decomposable subcubic graphs In this section, we focus on characterizing which subcubic graphs are decomposable. Moshi [ 16 ] showed the following result regarding decomposable cubic graphs. Theorem 7 (Moshi, 1989) . If G is a connected cubic graph that is not isomorphic to K_{4} or K_{3,3} , then H is decomposable. Furthermore, he argued that every subcubic graph with at least 8 vertices is decomposable. Let \overline{\mathcal{D}} denote the family of subcubic graphs that are not decomposable. Note that K_{3} is the only cycle that belongs to \overline{\mathcal{D}} . Now, let G\in\overline{\mathcal{D}} such that G\neq K_{3},K_{4},K_{3,3} . Our objective will be to characterize the structure of such a graph G . First, note that G is 2 -edge-connected and, since G\neq K_{3} , we have that \Delta(G)=3 . Also, by Theorem 7 , we have that \delta(G)=2 . We call a path, in G , subdivided if it contains at least two edges, the ends of the path have degree at least three in G , and every internal vertex in the path have degree two in G . Observe that every subdivided path in G has exactly two edges, otherwise, G has a matching cut. Thus, G satisfies the following property: 1. every vertex of degree two is adjacent only to vertices of degree three in G . In what follows, we relate the study of nondecomposable subcubic graphs to the study of nondecomposable cubic multigraphs (graphs that may contain parallel edges and loops). In this regard, given a subcubic graph G which is not a cycle, if we replace every subdivided path with an edge, then we obtain a cubic multigraph. Let \mathcal{C}(G) be the graph obtained