![](/files/happy5.png)
Matching cut and girth
Question For every
does there exists a
such that every graph with average degree smaller than
and girth at least
has a matching-cut?
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
![$ d $](/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png)
![$ g $](/files/tex/4239ee4145983e1d8ad375f0606cc7140bce36a3.png)
Let be a graph. A matching
is a matching-cut if there exists a set
such that
. Graphs having a matching-cut are called decomposable.
It is known that every graph with is decomposable [BFP11].
Bibliography
[C84] V. Chvátal, Recognizing decomposable graphs, J Graph Theory 8 (1984), 51–53
[BFP11] P. Bonsma, A. Farley, A. Proskurowski, Extremal graphs having no matching cuts, J Graph Theory (2011)
* indicates original appearance(s) of problem.